St. Theodosius Russian Orthodox Cathedral opened in 1913 and cost approximately $70,000 to construct. Most of the land-acquisition and building funds came from parishioners. However, it is believed that Russia's Czar Nicholas II–the one whose entire family was murdered during the Revolution of 1917–also contributed. Cleveland architect Frederick C. Baird designed the church, modeling it after the Church of our Savior Jesus Christ in Moscow. St. Theodosius's thirteen onion-shaped domes–actually one onion dome and 12 cupolas–represent Jesus and the 12 Apostles, and are a prominent part of the Tremont skyline. St. Theodosius was the site for a number of scenes in the 1978 movie "The Deer Hunter."
The first Orthodox parish in Cleveland, St. Theodosius was founded in 1896 by a small group of Carpatho-Rusins whose religion was called Greek Catholic. These people were not Greek, but rather emigrants from Austria-Hungary who changed their religious loyalty from the Pope in Rome to the patriarch of the Russian Orthodox Church–thus re-aligning themselves with Russian, rather than Rusin, Orthodox Christianity. In the same year that the parish was founded, the group's religious society, the Russian Saint Michael Rosko Orthodox Society, purchased land at the corner of Literary Road and McKinstry Street (West 6th Street) and constructed a small, wood-framed building on the site that served as the parish's first church. The church's first pastor was Rev. Victor Stepanoff, a Russian priest sent to Cleveland by the Bishop of the Russian Orthodox Church of North America.
While the church was founded by Rusyns, St. Theodosius also ministered in the early twentieth century to several other ethnic groups that had not yet established their own ethnic churches. According to a 1901 article in the Cleveland Plain Dealer, parish membership including several hundred Rusyns, as well as "ten Russians, a few Greeks, and about 30 Syrians." Romanians also worshiped at the original building at Literary and McKinstry prior to the construction of St. Mary Romanian Orthodox Church on Warren Road in 1908.
The move to St. Theodosius's new home in 1913 symbolized the parish's rapid growth at the beginning of the 20th-century. The new cathedral, which has a cornerstone identifying the building as a Greek Catholic Russian Orthodox parish–that is, no longer under the auspices of Rome–was built during the tenure of the church's third pastor, Rev. William Lisenkovsky. The second pastor, who followed Rev. Stepanoff, was Rev. Jason Kappandze, whose grandson with the same name served the church as pastor in the 1990s. The first Rev. Kappandze served the parish from 1902-1908. In 1904, Rev. Kappandze, who was said to have come from a military family in Russia, received permission from the Czar of Russia to serve as a chaplain for Russian troops fighting in the Russo-Japanese War.