The Philippines’ ranking in Trends in International Mathematics and Science Survey (TIMSS) is indicative of how mathematics is taught in the classrooms. This descriptive research determined the performance of 12 BSMT and 17 BSMarE freshmen students in solving general mathematics problems. They were preselected cadets who enrolled in a Maritime School in the Philippines first semester school year 2009-2010. Two sets of test instruments of similar context and style were used as pretest and posttest. The selected problems included routine or nonroutine and multistep problem and within the context and level of the students. Result shows a significant improvement in the performance of both BSMT and BSMarE students and as a whole at 0.05 alpha. Further, students developed various heuristics which includes Guess and Test, Working Backwards, Act it Out, Use of Diagram, Use of Algebra, Direct Counting, and Systematic List. Significant performance of students in the posttest is an indicator of the effectiveness of the problem-based learning (PBL) approach. Exposing them to various routine and non-routine problems enable students to apply mathematical concepts and understanding into real life problem situations. This makes mathematics more relevant which enhanced students’ interest and level of performance in mathematics.