This paper presents a comparative analysis of prospective elementary teachers' mathematical problem solving-related beliefs in Cyprus and England. Twenty-four participants, twelve from a well-regarded university in each country, were interviewed qualitatively at the exit point of their undergraduate teacher education studies. Analyses revealed both similarities and differences in the ways in which prospective teachers in each country construe both mathematical problems and mathematical problem solving, indicating not only that their beliefs are culturally situated but also that the concepts of "mathematical problem" and "problem solving" have different meanings cross-culturally. Such findings challenge the received view in mathematics education research of definitional convergence with respect to both mathematical problems and problem solving. Some implications for policy making are discussed.