Eldənizlər sülaləsinin banisi olan Şəmsəddin Eldəniz qıpçaqlardan idi. Mirxond yazır: Məlumatlı tarixçilər xəbər verirlər ki, qıpçaqların ölkəsində qədim çağlarda belə bir adət var idi: əgər hər hansı bir tacir birdəfəyə 40 qul alsaydı, onlan satan ondan yalnız otuz doqquzunun pulunu alır, qırxıncını pulsuz verirdi". Belə olmuşdu ki, Sultan Mahmudun hakimiyyəti dövründə bir qul alverçisi 39 qulu satıb, qırxıncı qul üçün pul götürməmişdi. Həmin qul da Eldəniz olmuşdur.[18] Bəzi mənbələrə görə Eldənizin mənşəyi Qafqazdakı qıpçaqlardan, bəzilərinə görə isə Mərkəzi Asiyadan və Xorasan ərazisindəki qıpçaqlardan gəlməkdədir. Xarəzm tarixçisi Bahaəddin Məhəmməd ibn Müəyyəd Xarəzmşahların məktublarını qələmə aldığı əsərində Atabəy Cahan Pəhləvana aid bir məktubdan bəhs edərkən, atabəyin Xarəzm ordularının başında Taraza qədər gəlmiş qıpçaq Uran qəbiləsinin rəislərindən Kıranla "qohum olduğunu" yazmaqdadır. Xarəzm ordusuna keçənə qədər adı çəkilən qəbilənin böyük hissəsi müsəlman deyildi. Belə ki, qəbilə türk tanrıçılığına pərəstiş edirdi.[19]
Eldənizi qul kimi alan Səlcuq vəziri Sümeyrəminin 1122-ci ilin mayında sui-qəsdlə öldürülməsindən sonra Sultan Mahmud onun bütün var-dövlətini müsadirə etdirirdi. Eldəniz də sultanın xidmətinə keçdi. Sultan Mahmud Eldənizin bacarığını görüb, tərbiyəsini Əmir Nəsrə tapşırır. Tezliklə onu sultan mətbəxinə başçı qoydular. O, bu vəzifəsində ikən Sultan Mahmudu ölüm yaxaladı. Sultan II Toğrulun hakimiyyəti dövründə Eldəniz sultanın şəxsi məmlükləri sırasına keçirildi. Sultanın xanımı Mömünə xatun ona xüsusi iltifat göstərirdi.[20] 1136-cı ildə Sultan Məsud Arranı atabəy Eldənizə iqta torpağı verdi və o, Bərdəyə öz iqamətgahına yola düşdü. Eldəniz burada yerli əmirləri tezliklə öz tərəfinə çəkdi, sultan xidmətinə asılılıqdan çıxdı, saraya nadir hallarda gəlirdi. Yavaş-yavaş o, bütün Azərbaycana yiyələndi və xırda əmirlikləri özünə tabe etdirdi. Cüzcani yazır "Eldəniz Azərbaycan ərazini öz hakimiyyəti altına alıb, çoxlu işlər gördü və bu ölkədə onun fəaliyyətinin izləri hələ də qalmaqdadır".[21] Bununla müstəqil Eldənizlər dövlətinin və bu dövləti idarə edən Eldənizlər sülaləsinin əsası qoyuldu. Eldənizin ələ keçirdiyi torpaqlara daxil olan Naxçıvan paytaxt seçildi.[12]