thumb|Gibraltarinlahti 1700-luvulla tehdyssä kaiverruksessa. Gibraltarin historian varhaisiin vaiheisiin liittyvät neandertalinihmiset, joiden viimeisiin asuinpaikkoihin Gibraltar kuului. Antiikin aikana Gibraltarinvuorta pidettiin tunnetun maailman rajana, ja se oli toinen niin kutsutuista Herakleen pylväistä. Gibraltarista lähti 711 umaijadien Espanjan valloitus.
Muslimit perustivat 1160 Gibraltarin ensimmäisen kaupungin. Espanjalaiset valtasivat 1462 Gibraltarin takaisin muslimeilta. Espanjan perimyssodan aikana 1704 englantilais-hollantilaiset joukot valtasivat niemen Espanjalta. Gibraltar siirtyi pian sen jälkeen Englannille. Utrechtin rauhassa Espanja tunnusti Gibraltarin kuuluvan Englannille, mutta yritti tämän jälkeen vallata sen useasti takaisin itselleen.
Gibraltarista kehittyi 1800-luvulla merkittävä sotilastukikohta ja kauppakeskus, ja sen merkitys kasvoi entisestään 1869, kun Suezin kanava avattiin. Maailmansotien aikana Gibraltar oli merkittävä liittoutuneiden satama, ja toisen maailmansodan aikana sen siviiliväestö evakuoitiin Saksan valloituksen pelossa. Sodan jälkeen Francisco Francon hallinto alkoi vaatia voimakkaammin Gibraltarin liittämistä takaisin Espanjaan. Vuoden 1967 kansanäänestyksessä gibraltarilaiset äänestivät ylivoimaisella enemmistöllä säilymisestään brittien alaisuudessa. Protestiksi Espanja sulki Gibraltarin-vastaisen rajansa. Raja avattiin lopulta 1985, kun Britannia oli uhannut estää Espanjan jäsenyyden Euroopan yhteisössä. Gibraltarin talous on monipuolistunut 1900-luvun lopulla, ja se ei ole enää niin riippuvainen Britannian armeijan läsnäolosta.
Nimi Tarinan mukaan Gibraltaria alettiin kutsua nimellä Jebal Tarik, ”Tarikin vuori”, johon niemimaan nykyinenkin nimi pohjautuu. Lähteiden niukkuuden takia berberien valtausarmeijan kuvernööri Tarik ibn Zijad on kuitenkin jäänyt arvoitukseksi, eikä varmuutta ole edes siitä nousiko armeija 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.
Esihistoria ja varhaiset vaiheet thumb|215px|Gorhamin luolasta on löytynyt neandertalinihmisen jäänteitä. Gibraltar on ollut viimeisiä paikkoja, joissa neandertalinihminen on asunut. Gorhamin luolasta on löytynyt neandertalinihmisen jäänteitä, jotka ovat vain 24 000 vuotta vanhoja. Merenpinta oli tuolloin huomattavasti matalammalla, ja Gibraltarinvuorta ympäröi rannikkotasanko. Neandertalinihmisen katoamisen jälkeisellä kivikaudella Gibraltaria asuttivat muun muassa Solutrén– ja Madeleinen kulttuurien nykyihmiset.
Gibraltarin ensimmäinen tunnettu nimi oli ”Calpe”, joksi foinikialaiset kutsuivat paikkaa. He eivät kuitenkaan asuttaneet Gibraltaria, vaikka todennäköisesti kävivätkin siellä usein. Kreikkalaiset pitivät sekä Gibraltarinvuorta että Afrikan puolella olevaa Monte Hachoa Herakleen töinä ja kutsuivat niitä Herakleen pylväistä, jotka merkitsivät myös tunnetun maailman rajaa.Kellerman, s. 11.
Arabivalloitus
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.Collins, 1989, 31–32
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.
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. Collins, 1989, 61
Gibraltar kuului 1000-luvulla muslimien Sevillan kuningaskuntaan. 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 vuonna 1160.
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. Gibraltar joutui jälleen muslimien haltuun vuonna 1333 neljän ja puolen kuukauden piirityksen jälkeen. Myöhemmin Gibraltaria hallitsivat ensin Merinidit ja sittemmin Nasridit. Heidän aikanaan rakennettiin niin sanottu Moorish Castle, eli maurilinnoitus.
Espanjan hallussa 1462–1704 thumb|215px|Isabella Katolilaisen myöntämä alkuperäinen Gibraltarin vaakuna. Medina Sidonian herttua valloitti vuonna 1462 Gibraltarin takaisin kristityille Reconquistan aikana ja päätti näin maurien 750 vuotta kestäneen vallan. Kaupunki jäi aluksi herttuan haltuun, mutta kuningas Henrik IV yhdisti sen nopeasti viereisiin kaupunkeihin ja muodosti näin Campo de Gibraltarin alueen. Gibraltar palautui vuonna 1468 Medina Sidonian herttualle, joka myi vuonna 1474 sen kahdeksi vuodeksi Pedro de Herreran johtamille juutalaisille. Herttua karkotti kuitenkin juutalaiset vuonna 1476.
Kuningatar Isabella Katolilainen määräsi vuonna 1501 Gibraltarin kuuluvaksi Espanjan kruunulle. Seuraavana vuonna hän myönsi Gibraltarille vaakunan, joka sillä on edelleen käytössä.
Barbareskimerirosvot tekivät vuonna 1540 ryöstöretken huonosti puolustettuun Gibraltariin. Tämän jälkeen keisari Kaarle I määräsi suojamuurin rakennuttamisen. Kuningas Filip II laajennutti muurin muutaman vuoden päästä ulottumaan Gibraltarinvuorelle. Hollannin laivasto yllätti 25. huhtikuuta 1607 espanjalaiset ja tuhosi Gibraltarin meritaistelussa muutamassa tunnissa koko Espanjan laivaston.
Siirtyminen brittihallintoon Valtaus ja takaisinvaltausyritykset 1700-luvulla Espanjan perimyssodan aikana amiraali George Rooken johtamat englantilais-hollantilaiset joukot tunkeutuivat maihin 21. heinäkuuta 1704 ja eristivät niemen muusta mantereesta. Gibraltarin kuvernööri ei kuitenkaan suostunut antautumaan, ja 23. päivänä englantilaisten laivasto tulitti kaupunkia usean tunnin ajan. Seuraavana päivänä Gibraltar antautui. Georg von Hessen-Darmstadt julisti tämän jälkeen niemimaan kuuluvan arkkiherttua Kaarlelle.Kellerman, s. 12.
thumb|left|180px|John Singleton Copleyn maalaus vuosien 1779–1783 piirityksestä. Gibraltarin valtauksen tarkoituksena oli saada Habsburg-sukuinen hallitsija Espanjaan. Englannilla oli kuitenkin muita suunnitelmia, ja maa halusi saada sotilastukikohdan Välimerelle turvatakseen kauppareittejä. Ensimmäinen englantilainen kuvernööri saapui syyskuussa 1705. Kuningatar Anna julisti 17. helmikuuta 1706 Gibraltarin vapaasatamaksi, ja se siirtyi vuonna 1713 virallisesti Englannille Utrechtin rauhassa.
Espanja pyrki useasti 1700-luvulla valtaamaan Gibraltarin takaisin. Yrityksistä tunnetuin on vuosien 1779–1783 piiritys.Encyclopædia Britannica. Britannian asevoimat olivat heikentyneet Yhdysvaltain vapaussodan takia, joten Espanja käytti tilaisuuden hyväkseen ja julisti kesäkuussa 1779 sodan Britannialle. Gibraltarin kuvernööri oli tuolloin George Eliott, joka suunnitteli marraskuussa 1781 yllätyshyökkäyksen kannakselle olleita vihollisia vastaan. Eliott tiesi, että espanjalais-ranskalaiset joukot suunnittelivat hyökkäystä. Hän kuitenkin teki rynnäkön yöllä ja onnistui tunnissa tekemään merkittävää tuhoa vihollisjoukoissa. Britit menettivät rynnäkössä vain viisi sotilasta. Britannian ja Espanjan sota päättyi 17. joulukuuta 1783, eikä Gibraltaria ole tämän jälkeen yritetty vallata.
Kruununsiirtomaaksi 1830 Gibraltarista kehittyi 1800-luvulla merkittävä sotilastukikohta ja kaupankäynnin keskus. Napoleonin sotien aikana vuosina 1803–1815 Välimeren laivasto sai sen kautta tarvikkeita. Sotien aikana Britannia oli sijoittanut huomattavasti rahaa ja miesvoimia Gibraltarin linnoitusten vahvistamiseen. Britanniassa tajuttiin pian niemimaan merkitys Välimeren suulla, ja Gibraltarista tuli vuonna 1830 Britannian kruununsiirtomaa.Kellerman, s. 13–14.
Suezin kanavan aukaisemisen jälkeen vuonna 1869 Gibraltarin merkitys kasvoi entisestään, sillä Välimerta pitkin kulki suurin osa laivoista, jotka menivät Britannian siirtomaihin Itä-Afrikkaan ja eteläiseen Aasiaan. Gibraltarinvuoreen tehtiin 1900-luvun alussa tunneleita, jotka helpottivat liikkumista niemimaan länsi- ja itäosien välillä. Kaivettu maa käytettiin alueen laajentamiseen, ja Gibraltar laajeni noin 26 hehtaarilla.
thumb|Varhainen näkymä Gibraltarin satamaan Britannian laivaston telakan rakennustöiden aikaan n. 1890. Gibraltar oli maailmansotien aikana liittoutuneiden merkittävä merisatama. Toisen maailmansodan alussa Gibraltarin siviiliväestö evakuoitiin Britanniaan, Jamaikaan ja Madeiralle, jotta niemimaa voitaisiin linnoittaa mahdollisen Saksan hyökkäyksen varalta. Gibraltarilla oli vuonna 1942 yli 30 000 brittisotilasta. Asukkaiden palauttaminen alkoi vuonna 1944. Pääosa asukkaista oli palannut vuonna 1946, vaikkakin viimeiset palasi vasta vuonna 1950. Sodan aikana italialaiset tekivät Gibraltariin useita vedenalaishyökkäyksiä. Natsi-Saksan suunnittelema operaatio Felix Gibraltarin valtaamiseksi kaatui Espanjan haluttomuuteen päästää Saksan joukkoja maaperälleen.
Espanjan ja Britannian 1900-luvun erimielisyydet thumb|left|180px|Auton kylkeen maalattuja iskulauseita brittimielisten voitettua vuoden 1967 kansanäänestyksen. Gibraltarin tilanne ei heti toisen maailmansodan päättymisen jälkeen herättänyt suurtakaan mielenkiintoa, kun sekä Espanjan että Britannian intressit olivat muissa asioissa. Francisco Franco esitti kuitenkin jo vuonna 1950 espanjalaislehdessä vaatimuksen Gibraltarin palauttamiseksi Espanjalle. Samana vuonna Gibraltar sai ensimmäisen oman lakiasäätävän elimensä, kun sinne perustettiin lakiasäätävä neuvosto.
Britannia ja Espanja veivät 1960-luvulla Gibraltarin-kysymyksen Yhdistyneisiin kansakuntiin saakka. Espanja vaati Gibraltarin siirtomaavallan purkamista, ja asiasta järjestettiin vuonna 1967 jopa kansanäänestys. Brittihallinnon kannattajat voittivat äänestyksen ylivoimaisesti, sillä vain 44 äänestäjää yli 12 000:sta äänesti Espanjaan liittymisen puolesta.