Despite a focus on teaching mathematics through challenging, problem solving tasks, there has been limited research into student attitudes towards these learning experiences. To address this gap in the literature, we asked 52 Australian primary students who had recently experienced mathematics taught in this manner to convey their feelings about learning through problem solving. Adopting a qualitative, exploratory, research design, student participants completed a brief questionnaire, and a sub-set also contributed to follow-up focus groups. Thematic analysis of the questionnaire data revealed that three-quarters of students reported unambiguously positive attitudes towards problem solving, most others were ambivalent, and no students expressed negative attitudes. Younger students (Year 3/4) were more likely to express positive attitudes than older students (Year 5/6) and boys more likely to express positive attitudes than girls. Positive attitudes arose from students enjoying learning through problem solving, the perception that it supported their learning, and students thriving on challenge. Follow-up focus groups also reinforced the power of working collaboratively, particularly the importance of learning through discussions with peers, and opportunities to explore authentic and purposeful tasks. The findings help explain why students frequently have positive reactions to learning mathematics through problem solving.