In 1784, the first russian settlement ("Three Saints Bay") was established on Kodiak Island by Gregory Shelikhov. The creation of the Russian-American Company by Emperor Paul I in 1799 finally regularized the governance of Alaska, or Russian-American Company as it was officially known. After the establishment of the settlement, Shelikhov and his partner Ivan Golikov petitioned Catherine II and the Holy Synod of the Russian Orthodox Church to send missionaries to care for spiritual needs of the russian settlers as well as those Native Americans who had been baptized by the "promyshlenniki" (trappers) in Alaska and to preach Orthodox Christianity to the Native Americans. The Holy Synod responded by assembling a missionary team of four priests, two deacons, and two monks from the Valaam Monastery, located on Lake Ladoga, north of St. Petersburg. The Synod charged Archimandrite Joasaph Bolotov with the supervision of the mission, and after perilous journey of 293 days across European Russia and Siberia, the team reached Kodiak Island on September 24, 1794.

The mission began to bear fruit immediately. In 1794 the Three Saints church was founded in Old Harbor, the first Orthodox Church on North American Continent. The hieromonk Macarius (Makary) settled on Unalaska (the largest island in the Aleutian chain) but soon extended his work to twenty-four more islands. Macarius baptized some 2,500 Native Americans and blessed more then 536 marriages. The hieromonk Juvenaly penetrated to the inner regions of Alaska and converted some 5,000 people to the Orthodox faith, until he was killed in 1796 near Lake Iliamna, thus becoming the first martyr for Orthodoxy in the New World. By 1796, the missionaries had baptized a total of 12,000 Native Americans. The success of the initial mission prompted the Holy Synod to set up an auxiliary bishopric for Alaska (attached to the see of Irkutsk, the main see for all of Eastern Siberia). Archimandrite Joasaph was elected as the first Orthodox bishop of America. On the return trip to Alaska, however, the S.S. Phoenix, the ship on which Bishop Joasaph was traveling (along with Father Macarius and his assistant, Stephen) was shipwrecked off the coast of Unalaska, with no survivors. The work of the mission continued; in Kodiak, the church was staffed by hieromonk Athanasius and deacon Nectarius, who established a school for both Russian and Native American children. However, Deacon Nectarius was called to Irkutsk in 1805, and Father Athanasius returned to Valaam in 1825. The only member of the original team who remained in America was Father Herman. After the death of Joasaph in 1796, Father Herman founded a hermitage on Spruce Island (in the Aleutian chain). Although he retired from active missionary work, his exemplary life and acts of charity spread his renown throughout Alaska. Father Herman wasn't afraid to stand up to colonial authorities to defend the rights of the Native Americans, and when disease or famine struck the Aleuts, he whole-heartedly and single-handedly cared for the people. During his lifetime, and after his death in 1837, miracles were attributed to his intercession. In 1970 Father Herman was canonized by the Russian Orthodox Church in recognition of his saintly life and work in North America.

Orthodoxy continued to grow and gain roots in the Native American communities in Alaska. Proof of this was demonstrated when the Spanish authorities in Northern California captured a party of Orthodox Aleuts on hunting expedition. The Spanish pressured the Aleuts to convert to Catholicism, but the Aleuts refused, citing their previous conversion to Orthodoxy. One of the Aleuts, Peter, was tortured to death because of his refusal to renounce the Orthodox faith. The other Aleuts were later released unharmed by an order of the Spanish governor. Peter therefore became the second Orthodoxy martyr in the New World, and the first Native American to be canonized by the Orthodox Church.

The Orthodox mission received "new life" with the arrival of Father Ioann Veniaminov in 1824. Father Ioann and his family settled in Unalaska where he continued Macarius' work; he devised an alphabet for the Aleuts, and then proceeded to translate the Scriptures into Aleutian. He also composed catechism in Aleutian entitled, "A guide to the Kingdom of Heaven". In 1834, he moved to Novoarkhangelsk (now Sitka) to work among the Tlingit Indians. After the death of his wife, he was consecrated as bishop of Alaska in November 1840. Following Russian Orthodox custom he had first been tonsured as a monk, and assumed the name of Innocent. Upon his return to Alaska, Bishop Innocent founded a seminary (1841) in Novoarkhangelsk and continued to open more schools and orphanages for the children of the region. Any Alaskan resident, regardless of ethnic background, was allowed to enroll at these schools and to receive an education. Instruction was carried out both in Russian and in the local languages. Bishop Innocent also expanded the territory covered by the Alaskan diocese; new mission centers were set up deep in the Alaskan interior, at Nusagag on the Kuskokwim River (1842) and Kenai on the Yukon (1845). By 1850, the Alaskan diocese consisted of 36 parishes with 12,000 communicants. The work of translating the Scriptures, the service books, and the catechism into Tlingit, Aleutian, and other local languages was augmented by the labors of Father Elias Tiskov and Father Nadejdin.

Bishop Innocent was also given responsibility for the Kamchatka Peninsula and the Far Eastern Siberian territories, and in order to better serve the entire region, moved his see to Yakutsk in the winter of 1851-1852. He thereupon consecrated Father Peter, the rector of the seminary in Novoarkhangelsk, to be the auxiliary bishop for Alaska. In 1868, Bishop Innocent was elected to be Metropolitan of Moscow, becoming the highest-ranking clergyman within the Russian Orthodox Church. After his election Innocent continued to support the missionary activities of the Russian Church in Asia and America. He established the Siberian Missionary Committee to oversee the staffing of missions. In order to ensure a supply of high-caliber clergy for the missions, this Committee asked for clerical volunteers to serve ten years in the mission field. In return, the Committee paid generous salaries and guaranteed a full pension to the missionary on his retirement. As a result, the missions of the Russian Church received a steady stream of well-educated and motivated priests who were able to leave Russia and their homes because the Committee gave them the financial independence necessary for them to concentrate on mission work. Metropolitan Innocent died in 1879, and was canonized in 1977 as the "Apostle to America" because of his mission and labors.

Bishop Peter (Lysakov), Saint Innocent's successor as bishop of Alaska, held that post until 1867, when he was succeeded by Bishop Paul (Popov) (1867-1870). In that year, the Russian Empire sold its colony to the United States.

The Russians had build an outpost in Northern California in 1812, and the first Orthodox church in the continental United States was build at Fort Ross. Although the outpost was closed in 1841, the San Francisco area remained a magnet for russian immigrants. In 1867 the Russians in San Francisco established Holy Trinity Church (now Holy Trinity Cathedral). Finally, in 1870, an english-language Orthodox parish was created in New York by Father Nicholas Bjering, a convert to Orthodoxy.