In this paper we report on a small-scale comparative examination of prospective elementary teachers' beliefs about problem-solving in Cyprus and England. First year undergraduate students (13 from Cyprus and 14 from England) from a well-regarded university in each country were qualitatively interviewed at the commencement of their respective teacher education programmes. Data, which were analysed by means of a combination of theory- and data-driven coding, indicated that, in both countries, students entered university with beliefs about problems and problem-solving that were not only products of the cultures in which they were educated, but also frequently incommensurate with the problem-solving expectation of the curricular frameworks within which they would have to work as teachers. Also, the outcomes confirmed that, despite researchers' assumptions of definitional convergence, the expressions "mathematical problem" and "problem-solving" continue to be used differently across cultures. Some implications for teacher education are discussed.