The article reports the results of a longitudinal research study conducted in three mathematics classes in Czech schools with 62 pupils aged 12–18 years. The pupils were exposed to the use of selected heuristic strategies in mathematical problem solving for a period of 16 months. This was done through solving problems where the solution was the most efficient if heuristic strategies were used. The authors conducted a two-dimensional classification of the use of heuristic strategies based on the work of Pólya (2004) and Schoenfeld (1985). We developed a tool that allows for the description of a pupil’s ability to solve problems. Named, the Culture of Problem Solving (CPS), this tool consists of four components: intelligence, text comprehension, creativity and the ability to use existing knowledge. The pupils’ success rate in problem solving and the changes in some of the CPS factors pre- and post-experiment were monitored. The pupils appeared to considerably improve in the creativity component. In addition, the results indicate a positive change in the students’ attitude to problem solving. As far as the teachers participating in the experiment are concerned, a significant change was in their teaching style to a more constructivist, inquiry-based approach, as well as their willingness to accept a student’s non-standard approach to solving a problem. Another important outcome of the research was the identification of the heuristic strategies that can be taught via long-term guided solutions of suitable problems and those that cannot. Those that can be taught include systematic experimentation, guess–check–revise and introduction of an auxiliary element. Those that cannot be taught (or can only be taught with difficulty) include the strategies of specification and generalization and analogy.