The aim of this study was to determine if medical students categorised as having deep and strategic approaches to their learning find problem-based learning (PBL) enjoyable and supportive of their learning, and achieve well in the first-year course. Quantitative and qualitative data were gathered from first-year medical students (N = 213). All students completed the Medical Course Learning Questionnaire at the commencement and completion of their first year of medical studies. The instrument measured a number of different aspects of learning, including approaches to learning, preferences for different learning environments, self-efficacy, and perceptions of learning within PBL tutorials. Qualitative data were collected from written responses to open questions. Results of students’ performance on two forms of examinations were obtained for those giving permission (N = 68). Two-step cluster analysis of the cohort’s responses to questions about their learning approaches identified five clusters, three of which represented coherent combinations of learning approaches (deep, deep and strategic, and surface apathetic) and two clusters which had unusual or dissonant combinations. Deep, strategic learners represented 25.8% of the cohort. They were more efficacious, preferred learning environments which support development of understanding and achieved significantly higher scores on the written examination. Strongly positive comments about learning in PBL tutorials were principally described by members of this cluster. This preliminary study employed a technique to categorise a student cohort into subgroups on the basis of their approaches to learning. One, the deep and strategic learners, appeared to be less vulnerable to the stresses of PBS in a medical course. While variation between individual learners will always be considerable, this analysis has enabled classification of a student group that may be less likely to find PBL problematic. Implications for practice and suggestions for future research are proposed.