While there has been much research focused on beginning teachers; and mathematical problem solving in the classroom, little is known about beginning primary teachers' learning to teach mathematics through problem solving. This longitudinal study examined what supported beginning teachers to start and sustain teaching mathematics through problem solving in their first 2 years of teaching. Findings show 'sustaining' required a combination of three factors: (i) participation in professional development centred on problem solving (ii) attending subject-specific complementary professional development initiatives alongside colleagues from their school; and (iii) an in-school colleague who also teaches mathematics through problem solving. If only one factor is present, in this study attending the professional development focussed on problem solving, the result was little movement towards a problem solving based pedagogy. Recommendations for supporting beginning teachers to embed problem solving are included.