לרומאים הייתה גיברלטר ידועה כ-"Mons Calpe", שם שנגזר מהמילה הפיניקית "kalph" שמשמעותה "חלל", וזאת ככל הנראה בגלל המערות הרבות הנמצאות במקום. המקום היה ידוע היטב לגאוגרפים העתיקים, אבל אין עדות ארכאולוגית להתיישבות קבועה במקום בעת העתיקה. היו סיבות שגרתיות לכך שלא הייתה התיישבות בגיברלטר בימי קדם - המקום חסר מים מתוקים זמינים ואדמה פורייה. מיקומה הגאוגרפי, שבתקופות מאוחרות יותר נעשה לנכס אסטרטגי, לא היווה בעת העתיקה גורם משמעותי, משום שלא הייתה התמודדות על הכניסה לים התיכון בין המדינות בתקופה ההיא.
שלטון מוסלמי (711–1309, 1333-1462).
בשנת 681 יצאו צבאות בית אומיה מחצי האי ערב במטרה לכבוש את צפון אפריקה, המזרח התיכון וחלקים גדולים של מערב אסיה; תושבים מקומיים רבים התאסלמו, למשל הברברים בצפון אפריקה. מצר גיברלטר נעשו לגבול שבין צפון אפריקה המוסלמית והיספניה הנוצרית, וכך קיבלו משמעות אסטרטגית נוספת. היספניה התדרדרה למלחמת אזרחים במאה ה-8 כאשר סיעות ויזיגותיות מתמרדות נלחמו על הכתר, והדבר נתן למוסלמים הזדמנות לפלוש להיספניה.
נוכחות המוסלמית בגיברלטר החלה ב-27 באפריל 711 כאשר המצביא הברברי טאריק בן זיאד הנהיג את הפלישה הראשונית של הכוחות המורים מצפון אפריקה אל חצי האי האיברי. על פי המסורת, טאריק נחת לראשונה בצוק גיברלטר ומשם החל את כיבושו, אם כי סביר יותר להניח כי הוא נחת במקום סמוך אחר; שמה של גיברלטר בימים ההם, Mons Calpe, שונה ל"ג'בל אל טאריק" (جبل طارق; "הר טאריק"); במהלך השנים נשתבש השם והפך ל"גיברלטר".
גיברלטר בוצרה לראשונה בשנת 1160 על ידי הח'ליף הראשון משושלת אל-מוואחידון, עבד אל-מואמין, במטרה למנוע פלישה מהחוף על ידי המלכים הנוצריים של אראגון וקסטיליה. שמה של גיברלטר שונה שוב ל"ג'בל אל-פאת" ("הר הניצחון"), אך השם לא תפס. יישוב מבוצר, "מדינת אל-פאת" ("עיר הניצחון"), נבנה במדרונות העליונים של הצוק. לא ברור עד לאיזו רמה התפתח יישוב זה, כיוון שהממצאים הארכאולוגיים ששרדו ממנו הם מעטים.
במהלך סוף המאה ה-13 ותחילת המאה ה-14 לחמה קסטיליה במרינים ממרוקו ובנאסרים מספרד על השליטה במצר גיברלטר. מאבק זה (בספרדית: "la Cuestión del Estrecho") נחשב לפרק ראשי בהיסטוריה של הרקונקיסטה, כיבושה מחדש של ספרד על ידי הנוצרים. בשנת 1309 הועמדו מגיניה של גיברלטר במבחן במהלך המצור הראשון על גיברלטר. פרדיננד הרביעי, מלך קסטיליה וחיימה השני, מלך אראגון איחדו את צבאותיהם בשביל לתקוף את אמירות קורדובה כשהם שמים להם למטרה את אלמריה במזרח ואת אלחסירס, דרך מצר גיברלטר, במערב. ביולי 1309 הם הטילו מצור הן על אלמריה והן על גיברלטר, שבה הייתה אוכלוסייה של 1,200 איש, מצודה וביצורים בסיסיים. לאחר חודש נכנעו מגיניה, וגיברלטר עברה לידיים קסטיליאניות. פרדיננד וויתר על המצור על אלחסירס, אך המשיך להחזיק בגיברלטר תוך שהוא מגרש את התושבים המוסלמים ומיישב במקומם נוצרים. מבצר ומספנה נבנו בגיברלטר על פי הוראתו על מנת להבטיח את השליטה עליה.
בשנת 1315 ניסו הנאסרים מקורדובה להשתלט שוב על גיברלטר והטילו עליה מצור, אך נמלטו כשכוח קסטיליאני הגיע. 18 שנים לאחר מכן, בשנת 1333, איחדו הסולטאן הנאסרי של קורדובה, מוחמד הרביעי, והסולטאן המריני של פאס, אבו אל חסן עלי איבן עותמאן, את כוחותיהם והטילו מצור על גיברלטר כשלרשותם כוח צבאי גדול וגם צי ימי. בפעם הזאת אלפונסו האחד עשר, מלך קסטיליה לא יכול היה לארגן כוח צבאי לעזרת גיברלטר במשך כמה חודשים בגלל תקיפות של הנאסרים בגבולותיו ומחלוקות פוליטיות פנימיות. כשלבסוף הגיע כוח צבאי קסטיליאני ביוני 1333, הוא גילה שהתושבים המורעבים של גיברלטר נכנעו למורים. הקסטיליאנים הטילו מצור נוסף על גיברלטר, אך המצור נכנס למצב של קיפאון; מחד גיסא לא הצליחו הקסטיליאנים לשבור את ההגנה המורית ומאידך גיסא למגינים לא היה היכולת לפרוץ דרך הים ולהביא אספקה. פקטור נוסף שהשפיע על רצונם של הקסטיליאנים להביא לסיומו של המצור הוא שבמקביל למערכה בגיברלטר החלו מרידות נוספות בתוך קסטיליה עצמה. שני הצדדים הגיעו להסכם לפיו המורים ימשיכו להחזיק בגיברלטר אך יאפשרו מעבר בטוח לספינות קסטיליאניות; כמו כן הם ייאלצו לשלם סכום כסף גדול לקסטיליה. תוקף ההסכם היה ל-14 שנים.
גיברלטר נותרה בידיים מוסלמיות עד לשנת 1462, אך בשנים הללו עברה מהנאסרים מגרנדה למרינים מפס לסירוגין. בשנת 1374 מסרו המרינים את גיברלטר לנאסרים, ככל הנראה כתמורה על עזרה צבאית בדיכוי מרידות במרוקו. חיל המצב בגיברלטר התמרד כנגד הנאסרים בשנת 1410, אבל צבא נאסרי צר על גיברלטר בשנה שלאחר מכן וכבש את המקום בחזרה. בהמשך, שימשה גיברלטר בסיס לפשיטות על השטחים הנוצרים, דבר שהניע את אנריקה דה גוזמן, הדוכס השני של נייבלה, לערוך מצור על גיברלטר ב-1436. המצור היה אסון והסתיים עם אבדות רבות לנוצרים, ואנריקה עצמו טבע כשניסה להימלט דרך הים. גופתו נתגלתה על ידי המורים והם ערפו את ראשו ותלו אותו לראווה על חומות גיברלטר למשך 22 שנים.
שלטון המורים על גיברלטר בא לקיצו ב-1462, כאשר כוח קסטיליאני קטן בפיקודו של אלונסו דה ארקוס, מושל טריפה, ערך מתקפת פתע על גיברלטר. באותו הזמן היה המושל ורבים מהתושבים רחוקים בגלל טקס הכתרת הסולטאן החדש של גרנדה. לאחר מתקפה קצרה שבה חיל המצב של גיברלטר סבל מאבדות כבידות, החיילים נכנעו לחואן אלונסו, בנו של דה גוזמן, שהיה כעת הדוכס של מדינה סידוניה. התושבים המורים גורשו, וגיברלטר יושבה שוב בנוצרים.
שלטון קסטיליאני וספרדי (1462-1704).
זמן קצר לאחר כיבוש גיברלטר השיב אנריקה הרביעי, מלך קסטיליה לתושבי גיברלטר את הזכויות מהן נהנו בתקופת השלטון הקודמת של הנוצרים. בשנת 1474 הודח אנריקה הרביעי מהמלוכה על ידי האצולה והכמורה הספרדית, ואחיו החורג אלפונסו הוכרז למלך. לאחר מצור של 15 חודשים שהוטל על גיברלטר על ידי חואן אלונסו דה גוזמן הדוכס ממדינה-סידוניה, מאפריל 1466 ועד ליולי 1467, נכבשה גיברלטר מידי בלטראן דה לה קואווה, שהיה נאמנו של אנריקה הרביעי. כתגמול לדוכס מדינה-סידוניה, העניק אלפונסו לו אלפונסו את השליטה על גיברלטר. הוא מת בשנה שלאחר מכן, אבל בנו אנריקה הוכרז כמושל גיברלטר על ידי אנריקה הרביעי שהושב על כנו. בשנת 1474 מכר הדוכס החדש של מדינה סידוניה את גיברלטר לקבוצה של יהודים אנוסים מקורדובה וסביליה בהנהגת פדרו דה הררה. היישוב היהודי שם הגיע ל-4,350 אנוסים שאף הקימו חיל משמר משלהם, אך לאחר שנתיים גורשו משם על ידי דוכס מדינה סידוניה. מעמדה של גיברלטר התחזק כאשר בשנת 1478 חידשה איזבלה הראשונה, מלכת קסטיליה תואר אצולה של "מרקיז גיברלטר".
ב-2 בינואר 1492, לאחר חמש שנות מלחמה, נכנעה האמירות המורית האחרונה בגרנדה על ידי המלכים הקתוליים. גיברלטר שימשה בשנת 1497 כבסיס לכיבוש ספרדי של העיר מלייה בצפון אפריקה. לאחר שנתיים, הועמדו בפני אחרוני המורים של גרנדה הברירה להמיר את דתם לנצרות או להיות מגורשים. מעט המירו את דתם, אך הרוב עברו לצפון אפריקה דרך גיברלטר.
בשנת 1501 הפכה גיברלטר לרכוש הכתר בהוראת המלכה איזבלה הראשונה, ובשנה שלאחר מכן ניתן לה שלט אצולה משלה, שהחליף את שלט האצולה של מדינה סידוניה ועודנו משמש את גיברלטר כיום. בהרשאה המלכותית שנלוותה לשלט האצולה, הדגישה איזבלה הראשונה את מעמדה של גיברלטר כ"מפתח שבין ממלכתנו לבין הימים המזרחיים והמערביים" [הים התיכון והאוקיינוס האטלנטי]. משמעות זאת יוצגה בשלט האצולה על ידי מפתח מזהב הנתלה מהשער הקדמי של מבצר בעל שלושה מגדלים. הצו המלכותי חייב את השליטים הבאים של ספרד "להחזיק ולשמור על העיר הנ"ל לעצמם ובשליטתם; וששום ניכור אליה, או לחלקים ממנה, או לתחום השיפוט שלה... לעולם לא יגיע ממלכי קסטיליה".
בתקופה זו השם "גיברלטר" התייחס לא רק לחצי האי עצמו, אלא גם לערים לה לינאה דה לה קונספסיון, לוס בריוס, סאן רוקה ואלחסירס. במזרח גבלה גיברלטר בנהר גואדיארו, ובצפון גבלה בשכנות היישובים קסטלר דה לה פרונטרה, ג'ימנה דה לה פרונטרה, אלקלה דה לוס גזולס, מדינה סידוניה וטריפה. מהמאה ה-16 ואילך השם "גיברלטר" ייצג רק את העיר גיברלטר ואת חצי האי שלה.
תחת שלטון הכתר של ספרד ידעה גיברלטר מספר דעיכות. סופו של השלטון המוסלמי והכיבוש הספרדי של הנמלים הדרומיים הביא לירידה ניכרת בחשיבותה האסטרטגית של גיברלטר. אמנם לגיברלטר עוד נודעה חשיבות כלכלית בתחומי דיג הטונה וגידול גפנים, אך חשיבותה כמבצר צבאי נהייתה מוגבלת, ובמקומה העיר מרבלה הפכה לנמל העיקרי של ספרד באזור.
גיברלטר הייתה מקום מגורים לא פופולרי מסיבות שונות. על מנת להרחיב את אוכלוסייתה, נשלחו לגיברלטר אסירים על ידי ממלכת גרנדה, להם הוצע לשרת בחיל המצב שבגיברלטר במקום להיות בכלא. על אף זאת ביקש חואן אלפונסו דה גוזמן ("Juan Alfonso de Guzmán"), הדוכס השלישי של מדינה ידוניה, לשוב למשול על גיברלטר. בספטמבר 1506, לאחר מות המלכה איזבלה, שם דה גוזמן מצור על גיברלטר בציפייה ששעריה ייפתחו בפני צבאו במהירות. אך הדבר לא קרה, ולאחר מצור עקר בן ארבעה חודשים ויתר דה גוזמן על משאלתו. גיברלטר קיבלה את התואר "נאמנה ביותר" מידי ממלכת ספרד כהכרה בנאמנותה לכתר.
מתקפות שודדי ים ומלחמות עם כוחות אירופיים.