Before the Byzantine Empire came into existence, Persians and Greeks had taken turns settling in and invading the territory that would later become known as Constantinople. When the Greeks had finally wrested this territory away from the Persian empire around 478 BC, the surrounding territory knew peaceful settlement as a Greek city-state for roughly three centuries, during which time it could be presumed that the people, like their Athenian or Spartan counterparts, tended toward polytheistic worship. In 150 BC, this territory would become assimilated into the Roman empire through a peace treaty that guaranteed independence in exchange for monetary tribute. Maintaining its independence, the city-state of Byzantium navigated its way through the Pax Romana (“Roman peace”) that would endure well into the 2nd century AD.
Like many kingdoms in antiquity and leading into the Middle Ages, religious devotion was of great importance in nearly all aspects of life. Integrated into the Roman empire, the city-state of Byzantium maintained and even shared polytheistic beliefs into the 4th century AD until the rule of Emperor Constantine began in AD 306. Revolutionary in restructuring the Roman empire as a whole, he was responsible in part for the Edict of Milan in AD 313 that lifted persecution on Christian worshipers throughout the empire as well as moving the Roman capital out of Rome and into the city-state of Byzantium, renaming it Constantinople in AD 330. During this time, sentiment toward Christianity improved as reparations were paid back to those who lost due to past persecution. Some speculate that Constantine looked to reestablish and improve relations with Christianity, not as an act of good will or personal desire for social reform, but out of fear for what he believed the one true god
As time passed, however, and the influence of Christianity cemented its foothold within what would later become exclusively the Eastern Roman, or Byzantine, empire, rulers such as Theodosius I and Justinian the Great saw to reform policy even further. Whereas Christianity had become tolerated and accepted among the people of the Roman empire, Theodosius had steadily suppressed Roman public religious customs beginning in AD 381, two years after his rule began. By AD 393, he had completely outlawed public practice of Roman and non-Orthodox Christian worship in the Byzantine empire, and the entirety of the empire was declared a Nicene Christianity state that followed the affirmed doctrine from the Council of Nicea in AD 325.
However, despite this outlawing of Roman practices, other sects besides Eastern Orthodox Christianity persisted for several centuries: Nestorianism, Monophysitism, Arianism among others as well as altogether non-Christian religions such as Roman paganism and Judaism to a lesser extent, well into the 6th century AD. However, as time passed, due prominently to the destruction of most religious iconography by Leo III and the later restoration, many smaller sects of Christianity as well as Slavic pagans who had found their way into the empire slowly came into the fold of Eastern Orthodoxy. By the late 9th century AD, a majority of what remained of the Byzantine empire identified as Eastern Orthodox, and it became the official religion of the state in both name and spirit.