In Australia, as is the case in other countries around the world, the Early Childhood workforce is in the process of 'skilling up' to meet government demands related to quality service provision. This paper sets out to identify what constitutes effective teacher professional learning through mentoring. Guided by critical realism and social practice as theoretical perspectives, the paper uses data drawn from the "State-wide Professional Mentoring Program for Early Childhood Teachers" (2011-2014), Victoria, Australia. The findings identify four C's essential to effective professional learning--Context: the association between individual aspirations and systemic requirements; Collegiality: the positioning and importance of collegial relationships; Criticality: critical deliberation in 'safe' learning environments; and Change: recognition that teacher learning takes place in the domains of professional dispositions, pedagogical knowledge and social capital. These findings point to the need to consider teachers' contexts of practice in the design of professional development programs such as mentoring, and to conceptualise learning as a socially situated practice rather than a detached pedagogic event.