Medical practice is changing, and the foundations of the paradigm shift lie in the development in research over the last four decades. Today, it is no longer adequate to treat a patient purely on clinical experience alone without a clear demonstration of evidence based on research, particularly the use of randomised controlled clinical trials. What is thought to be an effective mode of treatment currently may not necessarily hold true by the time medical students begin his/her medical practice. As a consequence, many medical schools worldwide are increasingly promoting evidence-based medicine (EBM) teaching in their medical curriculum along with problem-based learning (PBL). Teaching of EBM requires a paradigm shift in itself, as students must possess additional skills that are not traditionally part of medical training. These include the ability to acquire the skills in 'means of answering questions' than just 'knowing the answer to questions'. This paper aims to describe what EBM is and to highlight the formative experience of the teaching of EBM at the medical undergraduate level in the University of Malaya. Challenges and opportunities towards successful adoption of evidence-based practice are discussed.