What is the nature of religion and state relations in authoritarian regimes? How do religious and regime actors negotiate the terms of their relationship; what do the two sides want from one another; and how cooperative or conflictual are their interactions? To address these questions, the author compares religion-regime relations in contemporary Russia and China—two autocracies with long histories of religious repression, diverse religious profiles, and distinct relations between religion and the state. The article introduces a new theoretical framework anchored in interests and subnational authoritarian politics to explain how religious and political authorities negotiate their relationship and the constraints and opportunities that shape their interaction. Although there are many reasons to expect different types of religion-regime relations across Russia and China, the data demonstrate that subnational governments and diverse religious actors often forge innovative partnerships to govern more efficiently, gain access to resources, and safeguard their survival.