"I believe in one, holy, catholic, and apostolic Church" nearly all Christians who claim any sort of apostolic origin recite on Sundays. Among them are the various kinds of Orthodox Christians of the Eastern Churches. One friend, a Russian Jew born in Orthodoxy who left after falling victim to ethnocentrism, could not quite understand why they said that they believe in the "catholic" Church while not being Catholic. But they do believe they are the Catholic Church, and Orthodox, too.
The birth of "Orthodoxy" and the "Orthodox Church" is one of the minor mysteries in religious linguistics probably worthy of some level of study. The Church of Constantinople—as the Church of Rome, and the Church of Alexandria, and the Church of Aberdeen—believed itself to possess those four marks of the Church and hence to be a part of the Church Christ founded. That Church has gone by a few different names in its two thousand year history, but only a few. St. Ignatius of Antioch wrote in his letter to the Smyrnaeans
"Where ever the bishop is let the multitude of the people be, as where there is Jesus Christ there is the Catholic Church."
That phrase, Catholic Church, went on the shelf for the better part of the next few centuries, only coming off when the concept of "Christian" was no longer sufficient to distinguish the true Church from the odd sects engendered by heterodox thinkers or gnostic divines. "Christian," meaning "little Christs"—itself meaning "little anointed ones," a strong indication of Confirmation—by the fourth century had the same general meaning it has today. Anyone who professes Jesus Christ in some meaningful way is a Christian. Those who professed the true faith claimed membership in the "Catholic Church."
"Catholic" lived on in the Creed of Nicaea in the condemnation at the end:
"But those who say 'There was once when he was not,' and 'Before his generation he was not,' and 'He was made out of nothing,' or pretend that the Song of God is of another subsistence or substance, or created or alterable or mutable, the Catholic Church anathematizes."
Christians called the Church Catholic yet they did not always refer to themselves as Catholics. I can recall one occasion when St. Athanasius used the word Catholic substantially to describe individual believers. Most believers contented themselves with the label of Christian except for in the city of Constantinople, which, as the gateway to the east from the west and to west from the east, was the bottleneck of nearly every Christological controversy of the first millennium. Christians there described themselves as "orthodox" or "right worshippers" in contrast to the "heretic," the one who "chooses" to worship God according to his own will. The dialogues of the Greek Fathers crystallized this term in literary style and by the time of St. Theodore the Studite it was an accepted means of self-identification for the Christians of the Byzantine city. As an aside, the Roman Canon does pray for "omnibus orthodoxis.... cultoribus."
"Orthodox" signified an aesthetic, a type of Christian, a Christian who worshipped according to the rites of the Byzantine Church, who bore the scars of the heresies and the scabs of the triumphs that passed through Constantinople, and who adhered uniquely to the theology of the Greek Fathers. John Senior wrote that if philosophy is footnotes on Plato, theology is footnotes on St. Augustine. This phrase holds true only in the West. In the Greek tradition, theology is footnotes on the Cappodocian Fathers. Greek Christians prayed in the Great Entrance "May the Lord Our God remember all you orthodox Christians in His kingdom at all times...." and during the Litany of Fervent Supplication for "our orthodox fathers who here and elsewhere lie asleep in the Lord." While "orthodox" they certainly believed themselves part of the Catholic Church if not the Catholic Church. Then came the fall of Byzantium.
As political as the Roman Church was during the Middle Ages and Baroque era and as institutional as the Roman Church has been since Trent, the Constantinopolitan Church was before 1453 and more. The emperor was God's living representative on earth and the living icon of God the Father before whose image the citizens of Byzantium were to bow in reverence. He could call Councils, kidnap popes, replace the patriarch of his city, and—when he met little resistance—create Church laws that would mold the religious practice of his empire and beyond. Byzantium's triumph in Slavic lands buffered the empire from the west. The disaster of the fourth crusade and the decline of the Byzantine empire polarized Constantinople from "the West" when, hitherto, Constantinople had been more western than any eastern church. In the Palaiologian empire the Greek Church further distanced itself from "the West" during the Hesychast years of St. Gregory Palamas. Theology and liturgy became less communal and more mystical under the influence of Palamas and monastic patriarchs. Symbolism replaced realism in icons which now sat on the curtain around the Holy Place of the Hagia Sophia. Monastic patriarches replaced the organ, choral music, and the old Office with their own chants and psalter. The fall of Constantinople ossified the synthesis of the first millennium Constantinopolitan tradition with the Hesychast monastic movement, the last expression of "orthodox" Christianity.
In the midst of the newfangled Islamic city and without the institutional structures and imperial support the Greek Church previously enjoyed, Christians of Constantinople ceased to identify themselves as the Catholic Church. More troublesome to Greek Christians might have been Rome's unique hold over the title "Catholic Church." All that was left was the way of being Christian that they knew, orthodox. "Holy Orthodoxy" was born.
One potential pitfall to this argument is that some non-Byzantine Churches of the East that accept the Councils until and excluding Chalcedon are now called "Orthodox." Coptic Christians in my experience are very fervent about the denomination "Orthodox" while Armenians accept the title, but are more content for their church to be known as the "Armenian Apostolic Church." Perhaps the solution to this flaw in my argument lies in the popularity of the term "Orthodox" itself. Could the term have been spread by the Ottoman empire to denote Christians who had nothing to do with the Pope in Rome?
The question is an interesting one and worthy of further study.