With the growth in popularity of the object- oriented paradigm, the Department of Software Development at Monash University decided, two years ago, to teach object- oriented programming to the introductory programming students. The first year programming subjects were completely restructured and rewritten. It was decided to introduce the object-oriented paradigm after the students have had one semester of procedural programming experience in C++. Teaching object oriented principles in C++ has presented many challenges. The students find the complicated language syntax difficult. They also show a reluctance to move from the procedural to the object-oriented paradigm. However, with support and advice from education experts we have successfully addressed these problems. Different teaching approaches and techniques have been used. Small discussion classes were introduced to provide a forum for the consolidation of ideas presented in lectures, away from the distraction of computers. Extra support was given to the students in the form of a special World Wide Web page and a help desk. A concurrent research project has enabled close monitoring of the effectiveness of our teaching programme. In spite of the difficulties we have faced, the student results for 1995 and 1996 show an improvement in student performance over previous years.