This paper investigates profiles of high school students' mathematical problem-solving beliefs following the introduction of a new mathematics curriculum. In this quantitative study, 490 high school students responded to a mathematical problem-solving beliefs questionnaire to provide data about their beliefs related to mathematical problem solving. A cluster random sampling technique was used to select participants for the study. To accomplish the major goals of the study, a K-means clustering technique was conducted to analyze patterns that were discernible from their beliefs. In addition, a one-way ANOVA conducted to examine mean differences of their beliefs between clusters. Results revealed that, in general, students strongly believe that conceptual understanding is important in mathematics. In one of the clusters students hold strong beliefs about the usefulness of mathematics in their day-to-day lives while in another cluster it was strongly believed that effort was key for one to increase their mathematical ability. Results are important for students' confidence to solve mathematical problems and for implementation of a problem-solving approach in the new mathematics curriculum.