El cristianismo ortodoxo llegó al país en 1947 cuando llegó el arcipreste Vladimir Chekanovsky con el primer grupo de emigrados. Gracias a los esfuerzos de otro clérigo, el arcipreste John Baumanis, se fundaron parroquias ortodoxas rusas en Caracas, Valencia, Barquisimeto, Maracay y Barcelona. En los últimos años, han llegado a Venezuela varios sacerdotes nuevos desde Europa y Estados Unidos.
A principios de la década de 1950, se habían establecido parroquias ortodoxas en prácticamente todas las áreas del asentamiento ruso. Estas parroquias estaban bajo la jurisdicción de la Iglesia Ortodoxa Rusa Fuera de Rusia. La primera iglesia ortodoxa de Venezuela, la Iglesia del Signo de la Madre de Dios en Valencia, fue construida en 1950 por iniciativa de Vadim Ordovsky-Tanaevsky (padre de Rostislav) y según un diseño arquitectónico de V.E. Sheffer. En 1955 se consagra la Catedral de San Nicolás en la región de Dos Caminos de Caracas. Hasta el día de hoy, la catedral sigue siendo una parte integral de la vida espiritual rusa en Venezuela. Se construyeron dos iglesias de piedra adicionales en las provincias: San Pedro y San Pablo en Maracay y San Nicolás en Barquisimeto.[1]
Durante las décadas siguientes, las parroquias ortodoxas rusas sirvieron como punto focal de la vida espiritual de la diáspora rusa en Venezuela. Estas parroquias abrieron escuelas dominicales para los hijos de inmigrantes rusos. En la Catedral de San Nicolás de Caracas se instaló un palco para pagar los entierros de los pobres y en 1965 se tomó la decisión de comprar una sección del cementerio municipal.