This study aimed to investigate pre-service elementary mathematics teachers’ perceptions about mathematics problems and their beliefs about problem solving. The sample consisted of 244 senior undergraduate students studying in Elementary Mathematics Teacher Education programs at 5 different universities during the 2005-2006 academic years. The data were collected through a survey developed by the researcher. The results indicated that, in general, the pre-service teachers held positive beliefs about mathematical problem solving. However, they held several traditional beliefs about following predetermined sequence of steps while solving problems and the kind of problems emphasized in the new mathematics curriculum. Besides, they did not value problems that do not cover any topic in the curriculum, involve no number or take a long time to solve. In addition to these, the present study indicated that female and male pre-service teachers did not differ in terms of their beliefs about mathematical problem solving. However, the pre-service teachers’ beliefs showed significant difference when the universities attended was concerned.