This study investigated the effects of problem-based learning on students' beliefs about physics and physics learning and conceptual understanding of Newtonian mechanics. The study further examines the relationship between students' beliefs about physics and their conceptual understanding of mechanics concepts. Participants were 124 Turkish university students (PBL = 55, traditional = 69) enrolled in a calculus-based introductory physics class. Students' beliefs about physics and physics learning and their physics conceptual understanding were measured with the Colorado Learning Attitudes about Science Survey (CLASS) and the Force Concept Inventory (FCI), respectively. Repeated measures analysis of variance of how PBL influence beliefs and conceptual understanding were performed. The PBL group showed significantly higher conceptual learning gains in FCI than the traditional group. PBL approach showed no influence on students' beliefs about physics; both groups displayed similar beliefs. A significant positive correlation was found between beliefs and conceptual understanding. Students with more expert-like beliefs at the beginning of the semester were more likely to obtain higher conceptual understanding scores at the end of the semester. Suggestions are presented regarding the implementation of the PBL approach.