The details of the early conquest of Armenia by the Arabs are uncertain, as the various Arabic, Greek, and Armenian sources contradict each other. It was not until 645/646 that a major campaign to subdue Armenia was undertaken by Mu'awiya, the governor of Syria. Mu'awiya's general Habib ibn Maslama al-Fihri first moved against the Byzantine portion of the country: he besieged and captured Theodosiopolis (present-day Erzurum, Turkey) and defeated a Byzantine army, reinforced with Khazar and Alan troops, on the Euphrates. He then turned towards Lake Van, where the local Armenian princes of Akhlat and Moks submitted, allowing Habib to march onto Dvin, the capital of the former Persian portion of Anatolia. Dvin capitulated after a few days of siege, as did Tiflis further north in Caucasian Iberia. During the same time, another Arab army from Iraq, under Salman ibn Rabi'a, conquered parts Caucasian Iberia (Arran).

The Anatolian sources however provide a different narrative, both in chronology and in the details of the events, although the broad thrust of the Arab campaigns is consistent with the Muslim sources.