Background Despite being a well-established pedagogical approach in medical education, the implementation of problem-based learning (PBL) approaches hinges not only on educational aspects of the medical curriculum but also on the characteristics and necessities of the health system and the medical labor market within which it is situated. Aim To report our experiences implementing a PBL-based approach in a region of Brazil where: 1) all pre-university education and the vast majority of medical courses are based on traditional, lecture-based instructions; and 2) students’ career interests in primary care, arguably the prototypical PBL trainee, are heavily disfavored because of economics. Results Brazilian guidelines require that clinical training take place during the last 2 years of the medical program and include intensive, supervised, inpatient and outpatient rotations in pediatrics, family medicine, obstetrics and gynecology, internal medicine, and surgery. Throughout the pre-clinical curriculum, then, students learn to deal with progressively more difficult and complex cases – typically through the use of PBL tutors in a primary care context. However, because of curricular time constraints in the clerkships, and students’ general preoccupation with specialty practice, the continuation of PBL-based approaches in the pre-clinical years – and the expansion of PBL into the clerkships – has become exceedingly difficult. Discussion and conclusion Our experience illustrates the importance of context (both cultural and structural) in implementing certain pedagogies within one Brazilian training program. We plan to address these barriers by: 1) integrating units, whenever possible, within a spiral curriculum; 2) introducing real patients earlier in students’ pre-clinical coursework (primarily in a primary care setting); and 3) using subject experts as PBL tutors to better motivate students.