Maurien valta-aika Gibraltarilla
Maurien valta-aika Gibraltarilla kesti 727 vuotta, kauemmin kuin sitä seuranneet espanjalaisten ja brittien valta-ajat tähän mennessä. He perustivat monet kaupungin nykyisistä rakenteista, mutta useimmat rakennukset ovat tuhoutuneet tai vaurioituneet sotien ja piiritysten aikana, niiden päälle on rakennettu uusia tai niitä on muokattu niin että alkuperäistä rakennetta on vaikea tunnistaa.
Umaijadien sotapäällikkö Tarik ibn Zijad aloitti Espanjan valtauksen juuri Gibraltarilta. Espanjaa hallinneet visigootit olivat sekaannuksen tilassa, ja Ceutan visigoottikreivi Julian lupasi avustaa muslimeja Espanjan valloituksessa. Tangerin kuvernööri Tarik ibn Zijad lähti liikkelle Ceutasta ja rantautui Gibraltarille huhtikuussa 771. Gibraltarilla hän kokosi joukkonsa ja valtasi Pyreneiden niemimaan Roderikilta. Gibraltaria alettiin kutsua nimellä "Jebal Tarik", ”Tarikin vuori”, johon niemimaan nykyinenkin nimi pohjautuu.
Muslimivallan alkuvuosina Al-Andalusta eli muslimien hallitsemaa aluetta Iberian niemimaalla johdettiin Damaskoksesta käsin. Umaijadien dynastia jakaantui kuitenkin kilpaileviin osiin, ja Abd-al-Rahman pakeni Syyriasta Córdobaan vuonna 756. Hän perusti Córdoban emiraatin, josta tuli Córdoban kalifaatti. Vuoteen 1031 mennessä kalifaatti kuitenkin 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-Andaluksen 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.
Muslimien ja kristittyjen yhteenotot jatkuivat Pyreneillä, ja vuonna 1252 enää kaksi muslimikuningaskuntaa oli jäljellä. Vuonna 1309 Ferdinand IV oli piirittänyt Algecirasin ja havainnut Gibraltarin olevan haavoittuvainen. Hän lähetti Alonso Pérez de Guzmánin valtaamaan sen. Gibraltar antautui kuukauden piirityksen jälkeen. Se ei kuitenkaan pysynyt kristittyjen käsissä kuin muutaman vuosikymmenen ajan. Euroopassa oli ollut nälänhätiä ja kulkutauteja, ja muslimeilta vallatuille alueille oli vaikea löytää asukkaita. Kuningas Ferdinand IV:n vuonna 1310 laatima Gibraltarin peruskirja kuvastaa epätoivoa, sillä siinä sanotaan että kaupunkiin huolitaan kansalaisiksi kaikenlaista väkeä, jopa rosvoja, varkaita, murhaajia ja avionrikkojia. Turvapaikka evättiin vain maanpetokseen syyllistyneiltä.
Pohjois-Afrikkalaisiin berbereihin kuuluneet Merinidit valtasivat Gibraltarin vuonna 1333 neljän ja puolen kuukauden piirityksen jälkeen. Merinidien jälkeen Gibraltaria hallitsivat Grenadasta käsin valtaan nousseet Nasridit. Heidän aikanaan rakennettiin niin sanottu Moorish Castle, eli maurilinnoitus. Sen parhaiten säilynyt osa, "Tower of Homage" tai "Calahorra", oli pystytetty jo Almohadien aikana, mutta meronidit vahvistivat ja laajensivat sitä. He lisäsivät muureja, torneja ja portteja myös muualle Gibraltarin alueelle, ja kaupunki laajeni niiden suojissa. Se ulottui Gibraltarinvuorelta merenrantaan ja kattoi siis nykyisen Gibraltarin pohjoisimman osan. Kaupunki jakaantui kolmeen osaan: vanhaan kaupunkiin, linnoitettuun satamaan ja eteläosien asuinalueeseen, jota kutsuttiin nimellä Turba al Hamra, "punainen hiekka" mikä viittasi alueen maaperään. Linnoitusta ympäröivään vanhaa kaupunkiin eli kasbahiin pääsi vain yhden portin kautta; tuo portti on edelleen pystyssä ja sitä kutsutaan nimellä "Bab el-Granada", Granadan portti. Satama-aluetta suojasivat muurit ja tornit, ja sinne rakennettiin kolme porttia. Portit säilyivät myöhemmille ajoille, ja saivat vuorollaan espanjan- ja englanninkieliset nimetä. Niistä yksi johti maihin (Puerta de Espanja tai Landport), yksi merelle (Puerta de la Mer tai Casemates Gates) ja yksi asuinalueelle (myöhemmin Puerta de la Barcina tai Barcina Gate).
1300-luvun puolivälissä Kastilian ja Leónin hallitsija Alfonso XI yritti karkottaa muslimit. Hän uhrasi taisteluun varallisuutensa ja armeijansa, mutta onnistui lopulta valtaamaan Algecirasin kahden vuoden piirityksen jälkeen vuonna 1344. Kerättyään voimia jonkun aikaa hän keskittyi Gibraltarin valtausyrityksiin, mutta hyökkäys tyrehtyi vuonna 1350 kun Alfonso kuoli ruttoon.
Medina Sidonian herttua valloitti 1462 Gibraltarin takaisin kristityille Reconquistan aikana. Valloitus ajoittui Pyhän Bernhard Clairvauxlaisen juhlapäivään, ja hänen nimettiin kristityn Gibraltarin suojeluspyhäksi.