An der Wende vom 20. zum 21. Jahrhundert gelangten Vertreter des unabhängigen orthodoxen Klerus zu der Überzeugung, dass eine eigenständige kirchliche Organisation notwendig sei, die Reformen konsequent umsetzen und das synodale Leben entfalten könne.
Am 31. Januar 2000 wurde in Moskau auf einer Pressekonferenz die Gründung der gesellschaftlichen Bewegung „Für die Wiedergeburt der Orthodoxie“ bekannt gegeben.
Zu den Initiatoren gehörten Protopresbyter Gleb Jakunin, Metropolit Stefan (Linizki), Erzbischof Kiriak (Temerzidi) und der spätere Metropolit Witali (Kuschewatow).
Die Gründungserklärung verkündete die Notwendigkeit, zum apostolischen Modell der Kirchenleitung zurückzukehren.
Ihre Verfasser traten ein für die Dezentralisierung der kirchlichen Macht, die Wiederherstellung der Synodalität, die Eigenständigkeit der Gemeinden, den Verzicht auf die zwingende Bindung kirchlicher Jurisdiktion an Staatsgrenzen und die Überwindung übermäßiger administrativer Zentralisierung.
Besondere Aufmerksamkeit galt der Reform des gottesdienstlichen Lebens.
Vorgeschlagen wurde, die heutigen Landessprachen im Gottesdienst stärker zu verwenden, die Predigt zu einem festen Bestandteil jeder gottesdienstlichen Versammlung zu machen, einzelne rituelle Bräuche zu vereinfachen, übermäßig strenge Disziplinarvorschriften zu lockern und die Transparenz der kirchlichen Finanzen zu gewährleisten.
Die Gründer der Kirche betonten, dass die Erneuerung nicht auf eine Veränderung der dogmatischen Grundlagen des orthodoxen Glaubens ziele, sondern auf die Rückkehr des kirchlichen Lebens zu den Grundsätzen des Evangeliums.
Aus der Bewegung ging die Orthodoxe Kirche der Wiedergeburt hervor.
Am 13. Mai 2000 erhielt sie den Namen „Apostolisch-Orthodoxe Kirche“.
Mit diesem Namen wollten ihre Gründer die Kontinuität mit dem Glauben und der geistlichen Erfahrung der apostolischen Zeit sowie ihr Bekenntnis zur synodalen Ordnung hervorheben.
Erster Primas der Kirche wurde Metropolit Stefan (Linizki).