Over the past five decades Tanzania has hosted over two million refugees, about 200,000 of whom have been naturalized as Tanzania citizens. Children from this group face numerous challenges within the mainstream educational system. This paper considered education policy in Tanzania, with a specific focus on access to quality pre-primary education for children of naturalized refugees. It analyzes relevant policy documents published from 2006 -- the year before Tanzania started its latest refugee naturalization phase, to 2016. The 2014 Tanzania Education and Training Policy (ETP), the Pre-primary Curriculum, and the Pre-primary Schools Guide give the most focus to pre-primary education. Three National Five-year Development Plans considered all levels of formal education, except the pre-primary level. Findings revealed that policy documents articulate a commitment to providing equal educational opportunities for all people, regardless of their background, acknowledge existing problems with the educational system and make sensible recommendations. These include abolishing fees in all public schools; increasing flexibility in the choice and use of languages of instruction; decentralizing of program management and accountability; and, recommendations related to curriculum issues. However, the associated working documents do not suggest specific strategic and implementation plans to meet the intended goals, nor do they prioritize increasing educational participation for naturalized refugee children.