This paper explores how state and religious providers of education compete during the nation building process. Using novel administrative data, we characterize the evolution of Indonesia’s Islamic education system and religious school choice after the introduction of mass public primary schooling in the 1970s. Funded through informal taxation, Islamic schools competed with the state by entering in the same markets. While primary enrollment shifted towards state schools, religious education increased overall as Islamic schools absorbed growing demand for secondary education. In the short run, electoral support for the secular regime weakened in markets with greater public school construction. Over the long run, Islamic schools established at this juncture are more differentiated in terms of religious curriculum, and cohorts exposed to mass public schooling as children are more invested in religion than in the national identity. Our findings offer a new perspective on the political economy of education reforms and the emergence of parallel systems of public goods provision.