จากหลักฐานทางประวัติศาสตร์พบว่า เคยมีมนุษย์โบราณนีแอนเดอร์ทาล (Neanderthal) อาศัยอยู่ในยิบรอลตาร์เมื่อ 30,000-26,000 ปีก่อน โดยมีการค้นพบกระดูกของมนุษย์โบราณนีแอนเดอร์ทัล ที่ถ้ำกอร์แฮมส์ ซึ่งเป็นโพรงหินชายฝั่ง ด้านตะวันออกเฉียงใต้ของโขดหินยิบรอลตาร์ ทำให้ยิบรอลตาร์กลายเป็นแหล่งล่าสุดที่ค้นพบร่องรอยของมนุษย์โบราณนีแอนเดอร์ทัล นอกจากร่องรอยทางโบราณคดีดังกล่าวแล้ว ยังพบว่าชาวฟินิเชียเป็นกลุ่มแรกๆที่เคยอาศัยอยู่ในดินแดนยิบรอลตาร์ ในช่วง 950 ปีก่อนคริสต์ศักราช

หลังจากนั้นชาวโรมันได้เริ่มเข้ามาตั้งถิ่นฐานอย่างถาวร จนกระทั่งจักรวรรดิโรมันล่มสลายลง ดินแดนนี้จึงถูกปกครองโดยชาวแวนดัล ก่อนจะอยู่ในปกครองของราชอาณาจักรวิซิกอท ตั้งแต่ ค.ศ. 414 จนกระทั่งรัฐเคาะลีฟะฮ์อุมัยยะฮ์ได้แผ่ขยายอำนาจและบุกพิชิตคาบสมุทรไอบีเรียได้สำเร็จ ทำให้ดินแดนของราชอาณาจักรวิซิกอทตกเป็นของราชวงศ์อุมัยยะฮ์ ตั้งแต่ ค.ศ. 711 โดยดินแดนในคาบสมุทรไอบีเรียมีฐานะเป็นจังหวัดหนึ่งของรัฐเคาะลีฟะฮ์อุมัยยะฮ์

เดือนมกราคม ค.ศ. 750 รัฐเคาะลีฟะฮ์อุมัยยะฮ์ได้พ่ายแพ้ในยุทธการที่แม่น้ำซาบต่อราชวงศ์อับบาซียะฮ์ หลังพ่ายแพ้ในยุทธการครั้งนี้ เคาะลีฟะฮ์มัรวานที่ 2 ซึ่งเป็นผู้นำสูงสุดของราชวงศ์อุมัยยะฮ์ได้หลบหนีไปที่เมืองอะบูซีร ริมแม่น้ำไนล์ของอียิปต์ แต่ภายหลังถูกจับตัวได้และถูกสังหาร ทำให้ราชวงศ์อุมัยยะฮ์ล่มสลายลง ต่อมาอัส-ซัฟฟะห์ แห่งราชวงศ์อับบาซียะฮ์ได้ขึ้นเป็นเคาะลีฟะฮ์องค์ใหม่และได้สถาปนารัฐเคาะลีฟะฮ์อับบาซียะฮ์ขึ้นปกครองแทน

โดยกลุ่มผู้นำของราชวงศ์อุมัยยะฮ์ที่หลงเหลืออยู่นำโดยเจ้าชายอับดุลเราะห์มานที่ 1 ได้หลบหนีมาที่คาบสมุทรไอบีเรีย และท้าทายอำนาจของราชวงศ์อับบาซียะฮ์ด้วยการประกาศเป็นอิสระและประกาศตนเป็นเอมีร์แห่งกอร์โดบา ใน ค.ศ. 756 โดยดินแดนในคาบสมุทรไอบีเรียรวมทั้งยิบรอลตาร์ถือเป็นส่วนหนึ่งของอาณาจักรเอมีร์แห่งกอร์โดบา

ในปี ค.ศ. 929 สมัยของเจ้าชายอับดุลเราะห์มานที่ 3 ได้เปลี่ยนฐานะเป็นรัฐเคาะลีฟะฮ์แห่งกอร์โดบา โดยยิบรอลตาร์ถือเป็นส่วนหนึ่งของจังหวัดเซบิยา ต่อมาในปี ค.ศ.1023 จังหวัดเซบิยาได้แยกตัวจากรัฐเคาะลีฟะฮ์แห่งกอร์โดบาออกมาเป็นรัฐย่อยๆ (Taifa) และถูกปกครองโดยอาบู อัลกอซิม

ปี ค.ศ. 1091 เซบิยา ได้ถูกราชวงศ์อัลมูราบิตูน (Al-Moravids) จากโมร็อกโกยึดครอง ทำให้ยิบรอลตาร์ที่เป็นส่วนหนึ่งของเซบิยา กลายเป็นส่วนหนึ่งในดินแดนในปกครองของราชวงศ์อัลมูราบิตูน จากนั้นในปี ค.ศ. 1147 ราชวงศ์อัลมูราบิตูน ได้พ่ายแพ้สงครามในยุทธการที่มาร์ราคิชให้แก่ราชวงศ์อัลมูวาห์ฮิดูน (Almohads) และทำให้อัลมูวาห์ฮิดูนได้เข้ามาปกครองแทนที่

ในช่วงที่ยิบรอลตาร์อยู่ภายใต้ใต้ปกครองของ รัฐเคาะลีฟะฮ์อัลมูวาห์ฮิดูน โดยอับดุล อัลมุมิน เคาะลีฟะฮ์ผู้ปกครองดินแดนในสมัยนั้น ได้สร้างหอคอยขนาดใหญ่ขึ้นในบริเวณปราสาทมัวร์ (Moorish Castle) และให้ชื่อว่า มะดีนะฮ์ อัลฟัตฮ์ ซึ่งต่อมากลายเป็นโบราณสถานสำคัญ และถือเป็นแหล่งท่องเที่ยวที่มีชื่อเสียงแห่งหนึ่งของยิบรอลตาร์ในปัจจุบัน ในชื่อ เดอะทาวเวอร์ออฟฮอมิจ แห่งปราสาทมัวร์ (The Tower of Homage of Moorish Castle)

ในช่วงศตวรรษที่ 12 ยิบรอลตาร์ ถูกยึดครองหลายครั้ง ทั้งจากราชวงศ์นาสริดแห่งอาณาจักรเอมีร์แห่งกรานาดา ใน ค.ศ. 1237 และราชวงศ์มารินิดแห่งโมร็อกโก ก่อนที่จะมาตกอยู่ในอำนาจของราชบัลลังก์คาสตีล ใน ค.ศ. 1309 จากนั้นราชวงศ์มารินิดแห่งโมร็อกโกได้ยึดกลับคืนไปในปี ค.ศ. 1333 และกลับไปตกอยู่ภายใต้การปกครองของราชวงศ์นาสริดแห่งกรานาดาอีกครั้งหนึ่ง โดยราชบังลังก์คาสตีลพยายามจะตีคืนหลายครั้งแต่ไม่สำเร็จ

ปี ค.ศ. 1462 ราชบัลลังก์คาสตีลประสบความสำเร็จในการยึดยิบรอลตาร์คืนมาจากอาณาจักรกรานาดาได้ ภายใต้การบัญชาการรบของฮวน อลอนโซ เดอ กุสมัน แม่ทัพของคาสตีล