Kaynakların anlattığına göre, Eyyûbîlerin atası Şâdî b. Mervan önceleri Kuzey Azerbaycan’daki Şeddâdîler hanedanının hizmetinde çalışıyor, bugünkü Erivan yakınlarındaki Dvin’in Ecdânekan Kasabası’nda oturuyordu. Şeddâdîlerin yıkılması üzerine 1126 yılı civarında aşiretiyle Irak’a giderek Selçuklu saray ağalarından ve Bağdat şıhnelerinden arkadaşı Bihruz el-Hâdim’in hizmetine girdi. Bihruz el-Hâdim ise, onu kendi iktâı Tekrit’e vali tayin etti. Bir iki yıl sonra Şâdî ölünce yerine büyük oğlu Necmeddin Eyyûb getirildi. Tarihçi İbn Hallikan zamanında Şâdî’nin Tekrit’teki mezarı üzerinde bir türbe vardı.
Eyyûbîlerden kaynaklarda ilk defa 1131 yılında Musul Atabeyi İmadeddin Zengî’nin Tekrit yakınlarında Abbasî Halifesi Müsterşid-billah ve Karaca Sâkî kuvvetlerine yenilmesi dolayısıyla söz edilir. Bu yenilgi üzerine Tekrit Valisi Necmeddin Eyyûb, Zengî’nin Dicle Nehri’ni geçmesine yardım etmiş, bunun sonucu iki taraf arasında dostluk gelişmiştir. Nihayet, Salahaddîn Yusuf’un doğduğu 1138 yılında Eyyûbîler, Tekrit’den ayrılarak Musul’a gidip, Zengî’nin hizmetine girmişlerdir.
Eyyûbîler bundan sonra Zengî’nin ordusunda Haçlılara karşı savaşlara katıldılar. Zengî 1140 yılında Bikâ’ vadisindeki stratejik Balebek şehrini ele geçirince bu şehri Necmeddîn Eyyûb’a ikta verdi.
Onun böyle bir şehre vali tayin edilmesi Türkler arasında itibarlı bir emir (bey) olduğunu gösterir. Eyyûb’un kardeşi Esedüddin Şirkuh da ileri gelen emirler arasına katıldı. Urfa’nın fethinde bulundu. Zengî 1146 yılında Caber kalesini kuşatırken memlukları tarafından şehit edilince, devleti, oğulları Seyfeddin Gazi ve Nureddin Mahmud arasında paylaşıldı. Ali Küçük’ün desteğiyle Seyfeddîn Gazi Musul’da, Şirkuh’un desteğiyle Nureddîn Mahmud Halep’te yönetimi ele aldılar. Ba’lebek, Dımaşk kuvvetleri tarafından kuşatıldı. Yardım alamayan Necmeddin Eyyub, Dımaşk’taki idare ile anlaşıp, onların hizmetine girdi. Dımaşk’taki büyük emirler arasına katıldı.
Mimar Sinan Üniversitesi / Türkiye