This paper reports the results of an exploratory study of the perceptions of and approaches to mathematical proof of undergraduates enrolled in lecture-based and problem-based "transition to proof" courses. While the students in the lecture-based course demonstrated conceptions of proof that reflect those reported in the research literature as insufficient and typical of undergraduates, the students in the problem-based course were found to hold conceptions of and approach the construction of proofs in ways that demonstrated efforts to make sense of mathematical ideas. This sense-making manifested itself in the ways in which students employed initial strategies, notation, prior knowledge and experiences, and concrete examples in the proof construction process. These differences were also seen when students were asked to determine the validity of completed proofs. These results suggest that such a problem-based course may provide opportunities for students to develop conceptions of proof that are more meaningful and robust than does a traditional lecture-based course. (Contains 2 tables.)