Graduates are increasingly expected to perform multiple and varied tasks which require them to be critical enough to analyze problems, be creative enough to look for alternatives, and be practical enough to identify the most workable solution(s). The kind of roles and responsibilities one is expected to perform are ever increasing. This expectation has brought about the need to teach thinking skills, more specifically, higher order thinking skills to students. As a result, the teaching of thinking skills has increasingly gained attention from educators, in general, in the last few decades. In Malaysia, official attempts started in the early 1990s to teach thinking skills in schools and teacher education colleges. With far-reaching implications brought about by the knowledge economy the need to teach thinking skills has become even more evident, significant, and urgent. This paper will discuss the issues, challenges, and prospects in teaching thinking skills at institutions of higher learning. It will be based on formal attempts made at a selected institution of higher-learning. This paper would also dwell on the teaching and learning practices in relation to preparing future graduates to improve their thinking capabilities and also to teach higher-order thinking skills to others. Data for this paper would be drawn from research conducted on infusing thinking skills into the university curriculum (Rajendran, 2004) and perceptions of students taking a course on thinking skills (Rajendran, 2007). This paper would also offer recommendations to better improve the teaching of higher-order thinking skills to future graduates at institutions of higher-learning.