In this article, we analyse the problem-solving-related beliefs, competence and classroom practice of three Cypriot upper-primary teachers. Data derived from semi-structured interviews focused on teachers' beliefs about the nature of mathematical problems, problem-solving, and their competence as both problem-solvers and teachers of problem-solving; clinical interviews during which teachers solved a context-free geometrical problem, and observations of a lesson during which teachers introduced that problem to students of grade six. Analyses, structured by a framework derived from key problem-solving literature, indicated firstly, that the framework was an effective tool, sensitive to variation within and across the data from teachers, and secondly, that all participants, in largely explicable ways, exhibited consistency and inconsistency in the ways in which their beliefs, competence and practice interacted. Some implications for further research are discussed.