The Medieval history of Cyprus starts with the division of the Roman Empire into an Eastern and Western half.

After the division of the Roman Empire into an eastern half and a western half, Cyprus came under the rule of Byzantium. The cities of Cyprus were destroyed by two successive earthquakes in 332 and 342 AD and this marked the end of an era and at the same time the beginning of a new one, very much connected with modern life in Cyprus. Most of the cities were not rebuilt, save Salamis which was rebuilt on a smaller scale and renamed Constantia after the Roman Emperor Constantius II, son of Constantine the Great, residing in Constantinople. The new city was now the capital of the island. It was mainly Christian and due to this, some alterations were made during the rebuilding. The palaestra was turned into a meeting place and many architectural elements was used to erect spacious churches decorated with murals, mosaics, and coloured marble.

The main event in Cyprus in this period was the spreading of the Christian faith. At that time, its bishop, while still subject to the Church, was made autocephalous by the First Council of Ephesus. People were engaged very much in matters of faith, especially fighting the effort of the Eastern Orthodox Patriarch of Antioch to put the Church of Cyprus under his control. They were finally successful in 488, when Archbishop Anthemius guided by a dream discovered the tomb of Barnabas with the saint's body lying in a coffin and on his chest a copy of the Gospel of Matthew in Barnabas' own writing. Having the relics with him, Anthemius dashed to Constantinople and presented them to Emperor Zeno. The latter was very much impressed and he not only confirmed the independence of the Church of Cyprus but he also gave to the Archbishop in perpetuity three privileges that are as much alive today as they were then, namely to carry a sceptre instead of a pastoral staff, to sign with red ink and to wear a purple cloak during services. By the beginning of the 7th century, the patriarch of Alexandria was John the Merciful from Amathus. Another important Cypriot of the time is the church writer Leontios of Neapolis.

In 649 AD the Arabs made the first attack on the island under the leadership of Muawiyah I. They conquered the capital Salamis - Constantia after a brief siege, but drafted a treaty with the local rulers. In the course of this expedition a relative of Muhammad, Umm-Haram, fell from her mule near the Salt Lake at Larnaca and was killed. She was buried at that spot and the Hala Sultan Tekke was built there in Ottoman times. Under Abu'l-Awar, the Arabs returned in 650 and installed a garrison of 12,000 on part of the island, where they remained until 680.

After Uthman ibn al-Affan became caliph after Umar's death, Mu'awiya requested that the caliph allow him to build a navy to attack Cyprus, as Mu'awiya reasoned that Cyprus had become a satellite island of Byzantine forces which could threaten the caliphate on the western banks of Palestine. 'Ubadah, along with veteran companions of Muhammad such as Miqdad Ibn al-Aswad, Abu Dhar GhiFari, Shadaad ibn Aws, Khalid bin Zayd al-Ansari, and Abu Ayyub al-Ansari, all participated in building the caliphate's first Naval armada, led by Mu'awiya. Before he joined Mu'awiya's project to build first naval forces of the caliphate, 'Ubadah joined forces with Muslim general, Abd Allah ibn Qays. Together with Mu'awiya, they built the first caliphate armada with permission from ibn al-Affan. Abu Dharr mentioned that Miqdad ibn Amr al-Aswad participated in this project. Shortly later, Mu'awiya and 'Ubadah departed from Acre and headed to Cyprus. According to al-Baladhuri and Khalifa ibn Khayyat, Mu'awiya and 'Ubadah led the attack and were accompanied by their wives Katwa bint Qaraza ibn Abd Amr of the Qurayshite Banu Nawfal and Umm Haram. Umm Haram died in an accident during the campaign. The Muslim forces accepted Cyprus' surrender under the condition that they refrain from hostility to the Muslims, inform the caliphate of any Byzantine movements, pay 7,200 dinars annually for Jizya, and never reveal information to outsiders regarding the caliphate's military operations.

Mu'awiya and 'Ubadah forces pacified almost every Byzantine garrison. This is evidenced by two Greek inscriptions in the Cypriot village of Solois that note those two offensives. The entire island of Cyprus surrendered after their capital, Salamis, was surrounded and besieged. At least 50 military operations occurred in Cyprus between this first campaign in 648 until the last one in 650.

In 688, the emperor Justinian II and the caliph Abd al-Malik reached an unprecedented agreement. The Arabs evacuated the island, and for the next 300 years, Cyprus was ruled jointly by both the Caliphate and the Byzantines as a condominium, despite the nearly constant warfare between the two parties on the mainland. The collected taxes were divided among the Arabs and the emperor.

Under Basil I the Macedonian (r. 867–886) Byzantine troops recaptured Cyprus, which was established as a theme, but after seven years the island reverted to the previous status quo. Once again, in 911, the Cypriots helped a Byzantine fleet under admiral Himerios, and in retaliation the Arabs under Damian of Tarsus ravaged the island for four months and carried off many captives. The isolation of Cyprus from the rest of the Greek-speaking world assisted the formation of a separate Cypriot dialect. This period of Arab influence lasted until the 10th century.