We model two autocratic states facing internal and external threats, where religious clerics wield significant influence. Rulers allocate resources between internal security and the military while deciding whether to co-opt clerics to establish a state religion. Coopting reduces the risk of domestic unrest and allows a reduction in policing costs, freeing resources for the army. Surprisingly, equilibria are asymmetric across a wide range of parameters, with one state secularizing when the other adopts a state religion. Yet, in the presence of religious minorities aligned with foreign powers, state religions can become strategic complements, explaining the simultaneous emergence of nationally defined religions in rival states. The theory is illustrated using historical evidence from state formation in Europe and the Middle East.