This article looks at Taiwan’s policy towards religion to show that non-Western societies can also achieve what Alfred Stepan called a “twin toleration” wherein the state does not intervene in religious affairs, and religion does not seek to control the state. The paper shows the sets of constraints in which policy-makers struggling for an adequate way to deal with religion operate. They have to choose among a variety of models in democratic societies, to take into account the legacy of the authoritarian era, and to consider the specificities of Taiwan’s situation, influenced by a Chinese cultural heritage, Japanese colonialism and observations from other parts of the world. The paper then describes how these constraints have influenced the major stages in the evolution of relations between state and religions in Taiwanese society and then argue that the state had yet to reach a consensus up until 2008 on the legislation of religion because of disagreements between different religious actors.