Despite recommendations to incorporate mathematical problem solving into the practice of primary teachers there is little evidence of the widespread acceptance of such advice by Early Years teachers. Understanding teachers' perceptions of the obstacles they encounter when incorporating mathematical problem solving into their teaching can shed light on the matter. Survey responses of 22 teachers of Foundation and Year 1 across three Victorian schools indicated that the initial obstacles teachers perceived were those concerning children, teaching pedagogy, planning, resources, tasks and time.