This study explored students' mathematics-related beliefs and the relationship between the beliefs and their strategies for solving non-routine mathematical problems. The study was guided by Daskalogianni and Simpson's 2001 belief systems categories and strategies for non-routine mathematical problems. The participants were 625 grade 11 students from five high schools in Tshwane North District, Gauteng province of South Africa. Data were collected using a mathematics beliefs questionnaire, a mathematics problem-solving test and interview. Quantitative and qualitative research techniques were used for data analysis. It was found that the students held all the three belief systems (utilitarian, systematic and exploratory) at different degrees of intensity and the belief systems and strategies for problem-solving had a weak positive linear relationship, and there were no statistically significant differences among mean scores of the students holding systematic, exploratory and utilitarian beliefs. They apply unsystematic guess, check and revise; systematic guess, check and revise; systematic listing; looking for patterns; consider a simple case; modelling; logical reasoning; no logical reasoning; trial-and-error and use a formula in solving non-routine mathematical problems. Furthermore, it was found that the systematic belief system could explain the students' behaviour in problem-solving more than the exploratory and utilitarian belief systems.