Armenian presence in Cilicia dates back to the first century BC, when under Tigranes the Great, the Kingdom of Armenia expanded and conquered a vast region in the Levant. In 83 BC, the Greek aristocracy of Seleucid Syria, weakened by a bloody civil war, offered their allegiance to the ambitious Armenian king. Tigranes then conquered Phoenicia and Cilicia, effectively ending the Seleucid Empire. Tigranes invaded as far southeast as the Parthian capital of Ecbatana, located in modern-day western Iran. In 27 BC, the Roman Empire conquered Cilicia and transformed it into one of its eastern provinces.
After the 395 AD partition of the Roman Empire into halves, Cilicia became incorporated into the Eastern Roman Empire, also called the Byzantine Empire. In the sixth century AD, Armenian families relocated to Byzantine territories. Many served in the Byzantine army as soldiers or as generals, and rose to prominent imperial positions.
Cilicia fell to Arab invasions in the seventh century and was entirely incorporated into the Rashidun Caliphate. However, the Caliphate failed to gain a permanent foothold in Anatolia, as Cilicia was reconquered in the year 965 by Byzantine Emperor Nicephorus II Phocas. The Caliphate's occupation of Cilicia and of other areas in Asia Minor led many Armenians to seek refuge and protection further west in the Byzantine Empire, which created demographic imbalances in the region. In order to better protect their eastern territories after their reconquest, the Byzantines resorted largely to a policy of mass transfer and relocation of native populations within the Empire's borders. Nicephorus thus expelled the Muslims living in Cilicia, and encouraged Christians from Syria and Armenia to settle in the region. Emperor Basil II (976–1025) tried to expand into Armenian Vaspurakan in the east and Arab-held Syria towards the south. As a result of the Byzantine military campaigns, the Armenians spread into Cappadocia, and eastward from Cilicia into the mountainous areas of northern Syria and Mesopotamia.
The formal annexation of Greater Armenia to the Byzantine Empire in 1045 and its conquest by the Seljuk Turks 19 years later caused two new waves of Armenian migration to Cilicia. The Armenians could not re-establish an independent state in their native highland after the fall of Bagratid Armenia, as it remained under foreign occupation. Following its conquest in 1045, and in the midst of Byzantine efforts to further repopulate the Empire's east, Armenian immigration into Cilicia intensified and turned into a major socio-political movement. Armenians came to serve the Byzantines as military officers or governors, and were given control of important cities on the Byzantine Empire's eastern frontier. The Seljuks also played a significant role in the Armenian population movement into Cilicia. In 1064, the Seljuk Turks led by Alp Arslan made their advance towards Anatolia by capturing Ani in Byzantine-held Armenia. Seven years later, they earned a decisive victory against Byzantium by defeating Emperor Romanus IV Diogenes' army at Manzikert, north of Lake Van. Alp Arslan's successor, Malik-Shah I, further expanded the Seljuk Empire and levied repressive taxes on the Armenian inhabitants. After Catholicos Gregory II the Martyrophile's assistant and representative, Parsegh of Cilicia's solicitation, the Armenians obtained a partial reprieve, but Malik's succeeding governors continued levying taxes. This led the Armenians to seek refuge in Byzantium and in Cilicia. Some Armenian leaders set themselves up as sovereign lords, while others remained, at least in name, loyal to the Empire. The most successful of these early Armenian warlords was Philaretos Brachamios, a former Byzantine general who was alongside Romanus Diogenes at Manzikert. Between 1078 and 1085, Philaretus built a principality stretching from Malatia in the north to Antioch in the south, and from Cilicia in the west to Edessa in the east. He invited many Armenian nobles to settle in his territory, and gave them land and castles. But Philaretus's state began to crumble even before his death in 1090, and ultimately disintegrated into local lordships.