The Kalb tribe claim Yemenite descent; however, the Kalbites had settled in Syria and Western Iraq long before these regions were conquered by the Muslims. They served under the Ghassanids in defending Syria against the Sassanians; like the Ghassanids, the Kalbites had converted to Monophysite Christianity. The Kalbites clashed with the Muslims during the expedition to Dumat al-Jandal (located in south-western Iraq) in 627; two years later they sent a delegation to Muhammad declaring their conversion to Islam.
Under Muawiya, the first Umayyad caliph (661-680), the Kalb tribe became particularly influential in Syria. As Muawiya was married to the daughter of a Kalbite aristocrat, he chose to rely on their support in his conflict with Ali; Muawiya's son, Yazid, was also married to a Kalbite woman.
The Qays is a collection of clans which does not seem to have functioned as a unit in pre-Islamic times. Alleged common genealogies as well as lodging in garrison cites brought together various clans into something like a political party. Because of Muawiya and Yazid's reliance on the Kalb, the Qaysites supported Ibn al-Zubayr during his revolt (682-692). Upon the death of Muawiya II in 684, civil war broke out between the two groups in Syria; the Qaysites were defeated at Marj Rahit, just outside of Damascus in 684, and a new Umayyad caliph was installed. However, the cleavage between them only deepened, and raids and counter-raids continued well into to the reign of Abd al-Malik (685-705).
Hostilities recurred under the reign of Yazid II (720-724) when he openly favored the Qays, and again under the caliphs Walid II, Yazid III, and Ibrahim (743-744). During the conflict between the Umayyads and the Abbasids (750), 2000 Kalbites defected to the Abbasids, possibly because of Marwan II's almost exclusive reliance on the Qaysites.
The conflict between the Kalbites and Qaysites continued for centuries and was transferred to other territories, such as Africa, Spain, and Sicily.