From reading the research literature, it is evident that making the transition from pre-service teacher to beginning teacher is a challenging experience. New to the profession teachers can experience self-doubt and feelings of anxiety about meeting expectations. What is valued at the start of their career is support, especially if it is ongoing and tailored to their needs. In this paper, I present data from the first mentoring programme for new to the profession early childhood teachers in Victoria, Australia--the "State-wide Mentoring Program for Early Childhood Teachers" (SWMP) (2011-2014). I provide an overview of this mentoring programme highlighting aspects considered most effective in supporting beginning early childhood teachers. I propose that developing a mentoring programme incorporating respectful, responsive, reciprocal and reflective elements, can enhance both mentor's and mentee's professional development and professional identity. The impact of this programme is evidenced by the voices of the mentors and mentees involved.