Από την ίδρυσή της η Αποστολική Ορθόδοξη Εκκλησία επιδίωξε να ενώσει τις ορθόδοξες κοινότητες που συμμερίζονταν τις δογματικές και οργανωτικές της αρχές.
Το 2000 συνεχίστηκε η συγκρότηση της επισκοπής, εμφανίστηκαν νέες κοινότητες και άρχισε η επεξεργασία των εκκλησιαστικών καταστατικών και των κανόνων διοίκησης.
Την ίδια χρονιά η Εκκλησία αποφάσισε να τιμά τον πρωτοπρεσβύτερο Αλέξανδρο Μεν ως ιερομάρτυρα και διδάσκαλο του λαού.
Για μέρος των ιδρυτών της νέας Εκκλησίας η κληρονομιά του είχε ξεχωριστή σημασία. Το κήρυγμα του π. Αλεξάνδρου, η προσοχή του στα ζητήματα του σύγχρονου πολιτισμού, στον διάλογο με την κοινωνία και στη μόρφωση των πιστών έγιναν ένας από τους ηθικούς και ιεραποστολικούς προσανατολισμούς του κινήματος.
Το 2003 σημειώθηκαν ουσιώδεις αλλαγές στην ιστορία της Εκκλησίας.
Μέρος των αρχιερέων, με επικεφαλής τον Μητροπολίτη Στέφανο, εντάχθηκε σε άλλη εκκλησιαστική δικαιοδοσία των Αληθώς Ορθοδόξων.
Τη διοίκηση των κοινοτήτων της Αποστολικής Ορθόδοξης Εκκλησίας που διατήρησαν την αυτοτέλειά τους ανέλαβε ο Μητροπολίτης Βιτάλιος (Κουζεβάτοφ).
Υπό την προεδρία του συνεχίστηκε η οργανωτική συγκρότηση της εκκλησιαστικής ένωσης.
Στις 30 Απριλίου 2004 η Αποστολική Ορθόδοξη Εκκλησία καταχωρίστηκε στη Ρωσία ως κεντρική θρησκευτική οργάνωση με την επίσημη επωνυμία «Ένωση Ορθόδοξων Κοινοτήτων Αποστολικής Παράδοσης».
Έτσι κατοχυρώθηκε νομικά η θέση της εκκλησιαστικής δομής που ένωνε τις αυτοτελείς ορθόδοξες κοινότητες.