One of the challenges facing the Early Years (EY) sector is how to encourage more male practitioners to counterbalance a largely feminised workforce. Using case studies of male trainees at different stages of their primary undergraduate Initial Teacher Training course at one university, we attempt to consider data why there is under-representation of men within the leadership strata in EY settings. Questionnaires and interviews were conducted with the male sample groups and male leaders in primary schools to gain an overview regarding gender stereotyping. Our findings suggest that male trainees enjoy working in the EY sector, but they need mentoring by strong leaders to help them overcome the perceived contextual barriers of male stereotypes in that setting. In conclusion, we consider some of these barriers of stereotypes, attitudes, values, beliefs existing and the actions needed in addressing such stereotypes if a long-lasting change is to happen.