We conducted a 7-month video-based study in two sixth-grade classrooms focusing on teachers’ metacognitive and heuristic approaches to problem solving. All problem-solving lessons were analysed regarding the extent to which teachers implemented a metacognitive model and addressed a set of eight heuristics. We observed clear differences between both teachers’ instructional approaches. Besides, we examined teachers’ and students’ beliefs about the degree to which metacognitive and heuristic skills were addressed in their classrooms and observed that participants’ beliefs were overall in line with our observations of teachers’ instructional approaches. In addition, we investigated how students’ problem-solving skills developed as a result of teachers’ instructional approaches. A positive relationship between students’ spontaneous application of heuristics to solve non-routine word problems and teachers’ references to these skills in their problem-solving lessons was found. However, this increase in the application of heuristics did not result in students’ better performance on these non-routine word problems.