The progenitor of the Ayyubid dynasty, Najm ad-Din Ayyub ibn Shadhi, belonged to the Kurdish Rawadiya tribe, itself a branch of the large Hadhabani tribe. Ayyub's ancestors settled in the town of Dvin, in northern Armenia. When Turkish generals seized the town from its Kurdish prince, Shadhi left with his two sons Ayyub and Asad ad-Din Shirkuh.

Imad ad-Din Zangi, the ruler of Mosul, was defeated by the Abbasids under Caliph al-Mustarshid and Bihruz. Ayyub provided Zangi and his companions boats to cross the Tigris River and safely reach Mosul. As a consequence, Zangi recruited the two brothers into his service. Ayyub was made commander of Ba'albek and Shirkuh entered the service of Zangi's son, Nur ad-Din. According to historian Abdul Ali, it was under the care and patronage of Zangi that the Ayyubid family rose to prominence.