Problem-based learning (PBL) based on patient cases has become a well-established worldwide educational approach in medical education. Recent studies indicate that case-based PBL when used throughout an entire curriculum may develop into a counter-productive routine for students as well as teachers. Consequently, there is a need to develop PBL approaches further allowing students to work with more ill-defined problems and alternative learning structures. In this paper, we argue that this can be realised by introducing project-PBL into the medical curriculum, as in the medical education at Aalborg University, Denmark. We outline organisations of case- and project-PBL in the medical curriculum and present an explorative study of 116 first and second year students' experiences working in the two settings of PBL. Results reveal that students generally rate their PBL experiences positively however, project-PBL is rated more positively than case-PBL on all parameters studied. These results invite further consideration of the differences in working with cases and projects. Two central differences are discussed; the nature of the problem as the trigger of learning and students' possibilities for directing their own learning processes. The study demonstrates that introducing project-PBL may contribute significantly in problem-based medical education. However, the need for extensive research into advantages and limitations of the combined use of case- and project-PBL is also emphasised.