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 entered new markets, became more formal, and introduced more religious curriculum to compete with the state. 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, 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.