Qəbilənin adı “Qeysin (tanrı) qulu” mənasındadır. O, əvvəlcə Cənubi Ərəbistandakı əl-Arid bölgəsində məskunlaşan və şimal-qərbə doğru şimaldan Sudeyr və cənubdan əl-Xarca qədər uzanan əraziyə köç edən qəbilə qruplarına mənsub idi. Sonralar ərəb şəcərə ənənəsində bu qəbilələr şimal ərəb Məad konfederasiyasının bir qolu olan Rəbiə adlanırdı.

İslamdan əvvəlki dövrlərdə Əbdülqeys qəbiləsi tez-tez İrana basqın edirdi. Sasani şahı II Şapur (h. 309-379) ərəb qəbilələrinə qarşı ekspedisiyaya başçılıq etmiş və bu ekspedisiya zamanı Əbdülqeys qəbiləsinin əksəriyyətini qətlə yetirmişdir. Daha sonra bir neçə Əbdülqeys qəbiləsi Şapur tərəfindən İranın Kirman əyalətinə köçürüldü.

5-ci əsrə qədər Əbdülqeys qəbiləsi köçəriliyə keçərək cənubi Nəcddə (mərkəzi Ərəbistan) Tuveyq dağından kənarda məskunlaşdılar. 6-cı əsrdə qəbilə Şərqi Ərəbistandakı Əl-Əhsa və Qətif vahələrindən şimal-şərqə doğru köç etdi.

Ərəblərin İranı ələ keçirməsi zamanı xeyli sayda Əbdülqeys qəbiləsi cənub-şərqə daxil olaraq bölgəyə geniş basqınlar təşkil etdi. Əbdülqeys qəbiləsinin bir neçə dəstəsi İranın sahil dağlarında Təvvaz və Aşağı Mesopotamiyada Bəsrə yaxınlığında məskunlaşdı. 8-ci əsrin əvvəllərində 4000 Əbdülqeys qəbiləsinin döyüşçüsü Qüteybə ibn Müslümün Xorasana yürüşü zamanı ordusunun bir hissəsini təşkil edirdi.

Bəhreyndə Əbdülqeys qəbiləsinin şəcərələrində çoxlu boşluqlar və uyğunsuzluqlar var, buna görə də Baharna, ehtimal ki, etnik cəhətdən qarışıq əhalinin nəslindəndir.

Əbdülqeys qəbiləsi İslamın gəlişindən əvvəl daha çox xristian idilər.