人類の痕跡は古く、ネアンデルタール人の遺跡が発見されている。紀元前950年にフェニキア人がジブラルタルに初めて定住するようになった。その後もローマ人やヴァンダル族、ゴート族などがジブラルタルに訪れたが、どれも永住ではなかった。フェニキア人国家のカルタゴが第1次ポエニ戦争後にジブラルタルと南イベリア半島を勢力下としたのち、第2次ポエニ戦争によってローマ帝国がジブラルタルとイベリア半島を属領としたものの、400年代初期から西ゴート族がイベリア半島に居住するようになり、西ローマ帝国滅亡後は西ゴート王国の支配下となった。

711年、西ゴート王国はウマイヤ朝のターリク・イブン・ズィヤードに征服され、滅亡する。ムーア人の支配を受けてイスラム圏に入るが、およそ4世紀の間ジブラルタルが発展することはなかった。756年には後ウマイヤ朝が成立。変遷を経て1309年にナスル朝グラナダ王国の一部となる。カスティーリャ王国によって一時占領されるが、1333年にマリーン朝が奪還し、1374年マリーン朝はグラナダ王国にジブラルタルを割譲した。

1462年にメディナ・シドニア公がジブラルタルを奪取し、750年間に渡るムーア人の支配を終えた。 メディナ・シドニアは追放されたスペイン・ポルトガル系ユダヤ人にジブラルタルの土地を与え、コンベルソのペドロ・デ・エレアがコルドバとセビリアから一団のユダヤ人を移住させ、コミュニティが建設された。そして、半島を守るため駐屯軍が設立された。しかし、セファルディムとなったユダヤ人は数年後にコルドバか異端審問所に送還された。フェルナンド2世がスペイン王国を打ちたて、1501年にはジブラルタルもスペイン王国の手の下に戻った。同年にイサベル1世からジブラルタルの紋章が贈られた。

八十年戦争中の1607年にオランダ艦隊がスペイン艦隊を奇襲し、ジブラルタル沖が戦場となった（ジブラルタルの海戦）。この海戦でスペイン艦隊は大きな打撃を被った。1701年にスペイン王位継承で候補者の1人カール大公（後の神聖ローマ皇帝カール6世）の即位を後押しするオーストリア、イギリス、オランダがフランス王ルイ14世とスペイン王フェリペ5世に宣戦布告し、スペイン継承戦争が始まると、オーストリア、イギリス、オランダの同盟艦隊はスペイン南岸にある港町の襲撃を繰り返した。

1704年8月4日、ジョージ・ルーク提督率いるイギリスとオランダの艦隊の支援の下、オーストリアの軍人であるゲオルク・フォン・ヘッセン=ダルムシュタット（ヘッセン=ダルムシュタット方伯ルートヴィヒ6世の息子）指揮下の海兵隊がジブラルタルに上陸した。交渉の末、住民は自主退去を選択し、海兵隊はジブラルタルを占領した（ジブラルタルの占領）。フランス・スペイン連合軍はジブラルタル奪回のため艦隊をトゥーロンから派遣、それを阻止しようとルーク率いるイギリス・オランダ海軍が迎撃に向かい、フランス・スペイン海軍が撤退したことでジブラルタルは確保された（マラガの海戦）。

1713年4月11日にユトレヒト条約の締結によって戦争が終結するものの、その条約でジブラルタルはイギリス領として認められ、スペインは奪回の機を失った。アメリカ独立戦争中はスペインが独立軍の支援にまわり、1779年からジブラルタルへの厳重な封鎖を行った（ジブラルタル包囲戦）。イギリス軍は1782年に浮き砲台と包囲兵を撃破し、包囲網を破ることに成功した。翌年にはパリ条約に先立ち、講和が行われ、ジブラルタルは解放された。

1805年、トラファルガーの海戦ではイギリス海軍の拠点となった。その後、インドへのルートにスエズ運河の開通で地中海が加わり、蒸気機関を動力とする装甲巡洋艦などが海軍で普及すると給炭基地の役割も求められ、第一次世界大戦においてもジブラルタルが重要視されるようになった。

第二次世界大戦中もジブラルタル海峡の封鎖を行っていたフランスがドイツに敗北し、親独政権であるヴィシー政権が設立されフランス海軍がその指揮下に入ると、イギリス海軍H部隊がジブラルタルに配備された。トーチ作戦ではアメリカ軍もジブラルタルを拠点にした。なお、ドイツ軍はジブラルタルを陸路から攻略することを企て、フランシスコ・フランコ独裁下にあり中立国であったスペインに参戦と協力を要請したが、拒否された（フェリックス作戦）。

第二次世界大戦後は、東西冷戦がはじまるもイギリス海軍が役割を縮小すると同時にジブラルタルの軍事的役割も低下した。1967年にイギリス地中海艦隊が解体され、これに代わるアメリカ海軍第6艦隊はイタリアのガエータを拠点にしている。

しかし、1982年のフォークランド紛争や1986年のアメリカ空軍によるリビア爆撃で再びジブラルタルと基地の重要性が確認され、現在もイギリス海軍のジブラルタル戦隊 (Gibraltar Squadron) が駐留している。