Maurien valta-aika Gibraltarilla
Maurien ensimmäinen valtakausi 771–1309: Umaijadit ja almohadit

Umaijadien sotapäällikkö Tarik ibn Zijad aloitti Espanjan valtauksen mahdollisesti juuri Gibraltarilta Pohjois-Afrikan emiiri Musan määräyksestä. Espanjaa hallinneet visigootit olivat sekaannuksen tilassa, ja Ceutan visigoottikreivi Julian lupasi avustaa muslimeja Espanjan valloituksessa. Islamilaisen perimätiedon mukaan Julian oli lähettänyt tyttärensä Floridan Toledon hoviin Roderikin luo kasvatettavaksi. Hieman myöhemmin Florida väitti, että Roderik oli raiskannut hänet. Roderik torjui väitteen, mutta isä kääntyi Pohjois-Afrikan muslimien puoleen, joita yllytti hyökkäämään Roderikin kimppuun. Roderikin palatsissa oli huone, jonne kukaan ei saanut astua, ei edes kuningas.  Joka sinne menisi, vetäisi itsensä ja maansa päälle suuren onnettomuuden. Roderik kuitenkin meni huoneeseen, näki siellä arabeja esittävän muotokuvan ja luki ennustuksen, että vielä samana päivänä arabit tekisivät lopun hänen valtakunnastaan. Juuri näin tapahtuikin, kun kreivi Julianin yllyttämät muslimit nousivat maihin Gibraltarissa. Perimätiedon kertoo islamilainen historioitsija Ibn Abd al-Hakam (k. 871) yli sata vuotta itse tapahtumien jälkeen.
Tangerin kuvernööri Tarik ibn Zijad lähti liikkeelle Ceutasta ja rantautui Gibraltarille huhtikuussa 711. Valloittajat ehkä saapuivat hävinneen osapuolen kutsusta auttamaan vallanperimyskiistassa hävinnyttä osapuolta. Ensimmäistä valloitusarmeijaa johtanut kuvernööri Tarik ainakin löi helposti Roderikin armeijan, joka Vuoden 754 kronikan mukaan kärsi eripuraisuudesta. Musa nousi joukkoineen maihin Cadizissa ja eteni nopeasti sisämaahan.
Tarinan mukaan Gibraltaria alettiin kutsua nimellä Jebal Tarik, ”Tarikin vuori”, johon niemimaan nykyinenkin nimi pohjautuu. Lähteiden niukkuuden takia kuvernööri Tarik on kuitenkin jäänyt arvoitukseksi. Varmuutta ei ole edes siitä nousiko valtausarmeija maihin Gibraltarissa vai jossain muualla, esimerkiksi Cadizissa. Sitäkin on ehdotettu, että nimen ”Gibraltar” taustalla olisi latinan sana ”altus” eli korkea, joka olisi sitten kielitieteen tuntemaan tapaan kahdentunut arabiankielen korkeaa tarkoittavan sanajuuren g-b-r kanssa. Tällöin kuvernööri olisi saanut nimensä niemestä eikä päinvastoin.
Valloittajien uskonnosta ei ole varmuutta, sillä ainoa aikalaislähde, nähtävästi toledolaisen kirkonmiehen kirjoittama Vuoden 754 kronikka ei kuvaa tapahtumia uskonsotana vaan etnisenä konfliktina. Valloittajia ei kutsuta muslimeiksi vaan maureiksi, saraseeneiksi tai arabeiksi.
Arabivallan alkuvuosista lähtien Al-Andalus oli suhteellisen itsenäisesti hallittu alue, jonka arabialainen ei emiiri ottanut vastaan käskyjä Damaskoksesta saakka, vaikka muodollisesti olikin kalifin alamainen. Umaijadien dynastian kukistuessa vanhan hallitsijaperheen jäsenistä Abd-al-Rahman pakeni Syyriasta Córdobaan vuonna 756. Kolmenkymmenen sotavuoden jälkeen hän vakiinnutti valtansa melkein koko Andalusiassa. Córdoban emiraatti vaihtui 900-luvulla Córdoban kalifaatiksi, mikä merkitsi myös muodollista irtautumista Bagdadin auktoriteetista 1000-luvun alussa kalifaatti  hajosi kilpaileviin pieniin kuningaskuntiin eli taifoihin. Suurimmat näistä olivat Sevillan, Granadan, Toledon ja Zaragozan taifat. Gibraltar kuului Sevillan taifaan. Algecirasin kuvernööri pelkäsi pohjoisafrikkalaisten muslimien hyökkäystä ja perusti Gibraltarille linnoituksen. Ensimmäisen kaupungin paikalle rakensi vasta almohadikalifi Abd al-Mu'min. Hän kutsui kaupunkia nimellä Medinat al-Fath, voiton kaupunki, ja sen rakennustyöt alkoivat 1160. Kaupungin suunnittelusta vastasivat Al-Andalusin kuuluisimmat arkkitehdit. Kaupunkiin rakennettiin suuri moskeija, hallitsijan palatsi (joka ilmeisesti sijaitsi nykyisten kylpylän jäänteiden kohdalla), suojamuurit, tuulimylly, maanalainen vesisäiliö ja vesihuoltojärjestelmä sekä satama. Muurien suojaamasta kaupungista oli vain yksi kulkureitti mantereelle, Bab-al Fatuhiksi kutsuttu portti. Tuonaikaisen moskeijan paikalla on nykyisin Gibraltarin katedraali.