Problem solving is the highest level of cognitive skill. However, this skill seems to be lacking among secondary school students. Teachers' beliefs influence the instructional strategies used for students' learning. Hence, it is important to understand teachers' beliefs so as to improve the processes for teaching problem solving. The purpose of this study is to investigate beliefs of secondary school teachers in rural schools on problem solving in teaching. The sample were teachers selected from secondary schools in two rural districts in Malaysia. A survey of 75 secondary school teachers was done using the Learning Skills Questionnaire formulated for this purpose. The findings indicate that rural school teachers are aware of the usefulness of problem solving but still emphasize memorization of facts and concepts for learning. These might be because they are unaware of how to teach problem solving. Hence, further research is required in developing instructional strategies for teaching problem solving skills among rural school teachers. Further research could be done to determine whether there was a difference in beliefs among urban school teachers.