גיברלטר המוסלמית
הקרב על המצר

במהלך סוף המאה ה-13 ותחילת המאה ה-14 נלחמו הקסטיליאנים, המרינים ממרוקו והנאסרים מגרנדה על השליטה במצר גיברלטר. קרב זה (בספרדית: la Cuestión del Estrecho) מהווה פרק ראשי בהיסטוריה של הרקונקיסטה הנוצרית בספרד.
עם קריסתה של ח'ליפות אל-מוואחידון והתגברותן של המתקפות הנוצריות על חצי האי האיברי בין העשור השני לעשור הרביעי של המאה ה-13, עברה הגדה הצפונית של מצר גיברלטר לשליטתה של האמירות הנאסרית של גרנדה. בשנת 1274 (או 1275) העניק הסולטאן הנאסרי מוחמד השני את הערים אלחסירס וטריפה, וככל הנראה גם את גיברלטר יחד איתם, לח'ליף המריני אבו יוסף יעקוב כתשלום על תמיכתו בגרנדה נגד ניסיונות פלישה קסטיליאניים. המרינים ניסו להשיג לעצמם דריסת רגל בחצי האי האיברי ושליטה מוחלטת על הסחר במצר גיברלטר, ושלושת הערים הללו יועדו לשמש כבסיסים ימיים. בשנת 1292, כחלק ממאמציו להשיג את השליטה במצר גיברלטר, הטיל סנצ'ו הרביעי, מלך קסטיליה מצור על העיר טריפה וכבשהּ. שנתיים לאחר מכן, ב-1294, הטילו המרינים מצור על העיר אך העיר, תחת פיקודו של אלונסו פרז דה גוזמן, הצליחה לעמוד במצור ונותרה בידיים נוצריות. כתוצאה מכך החליטו המרינים לסגת למגרב ומכרו את הערים הנותרות, אלחסירס וגיברלטר, לגרנדה.
על אף שאין בנמצא מסמכים המתעדים את התקופה שלאחר פרויקט מדינת אל-פאת', יש סיבה להאמין כי עיירה מבוצרת קטנה התקיימה בגיברלטר, וכי עובדת קיומה היא תוצאה ישירה של נפילתה של טריפה בשנת 1292. המרינים ציפו שלאחר שכבש את העיר, ימשיך סנצ'ו השני מלך קסטיליה ויטיל מצור על אלחסירס (דבר שבפועל לא התרחש) במטרה לנתק את קווי האחיזה הישירים שלהם בחצי האי האיברי. קיומו המאיים של מבצר נוצרי ממערב הוביל לייסוד מבצר וחיל מצב ממזרח לאלחסירס. כך תוכל גיברלטר להגן על המשמר העורפי הנמצא באלחסירס ולהוות כוח עתודה אם אלחסירס תותקף. בד בבד, ועם הנוכחות הגוברת של ספינות נוצריות במצר, תוכל גיברלטר להוות נקודת תצפית מצוינת על המצר.
בשנים 1309–1310 איחדו פרננדו הרביעי, מלך קסטיליה וחיימה השני, מלך אראגון את צבאותיהם על מנת לתקוף את אמירות קורדובה. המאמץ העיקרי שלהם התרכז באלמריה במזרח ובאלחסירס, ובמקביל הטילו הקסטיליאנים גם מצור על גיברלטר. המצור היה קצר ונמשך מיולי ועד ל-12 בספטמבר 1309. המצור על גיברלטר אומנם צלח, אך המתקפה העיקרית של קסטיליה על אלחסירס כשלה. על פי הדו"ח הקסטיליאני שנמסר על המצור בגיברלטר, בעת ההתקפה שהו בגיברלטר רק 1,125 חיילים מוסלמים. לאחר שכבשהּ וגירש את אוכלוסייתהּ, הורה פרדיננד הרביעי לחזק את החומות בגיברלטר, לבנות מגדל עוז מעל העיר וכן מספנה בה יוצבו גליאות.
נפילתה של גיברלטר הביאה להדחתו של הסולטאן הנאסרי של גרנדה בידי אחיו נאסר. הסולטאן החדש הכריז על "ג'יהאד" נגד הנוצרים בחצי האי האיברי, אך במהלך תקופת שלטונו איבדו הנאסרים זמנית את השליטה באלחסירס וברונדה, ובשנת 1314 הודח נאסר על ידי אחיינו איסמעיל הראשון. בשנת 1315 הטיל איסמעיל הראשון מצור על גיברלטר, אך הוא נסוג מאחר שכוחות קסטיליאניים התקיפו באותו הזמן את גרנדה, וכך נותרה גיברלטר בידיים נוצריות.
ממלכת קסטיליה אחזה בגיברלטר למעלה מ-20 שנה, עד ל-1333, אז נרקמה ברית בין מוחמד הרביעי, סולטאן גרנדה ובין השליט המריני אבו אל-חסן עלי איבן עותמאן. צבא שמנה 7,000 חיילים בפיקודו של עבד אל-מליק, בנו של אבו אל חסן, הועבר בחשאיות דרך מצר גיברלטר ונפגש עם כוחותיו של הסולטאן הנאסרי מוחמד הרביעי בעיר אלחסירס בפברואר 1333. באותו הזמן הייתה ממלכת קסטיליה עסוקה בהכתרתו של אלפונסו האחד עשר כך שצבאותיה לא היו זמינים, וכן אוצרות המזון בגיברלטר היו מרוקנים עקב שחיתותו של המושל, דון וסקו פרז דה מיירה. המצור השלישי על גיברלטר נמשך 4 וחצי חודשים, וב-17 ביוני 1333 נכנע חיל המצב הנוצרי של גיברלטר.
מייד לאחר מכן, הותקפה גיברלטר על ידי צבא קסטיליאני גדול בניסיון להשיב את השליטה הנוצרית שם. לאחר חודשיים של מצור בהם לא הצליח אף אחד מהצדדים להגיע להכרעה, התפשרו הקסטיליאנים והמוסלמים וחתמו על הסכם הפסקת אש שאפשר לשני הצדדים לסגת בכבוד מהמצור. על אף שגיברלטר נותרה בידיים (ב-24 באוגוסט 1333) מוסלמיות על פי הסכם זה, הדבר עלה למוחמד הרביעי בחייו; ביום שלאחר חתימת ההסכם נרצח מוחמד הרביעי על ידי אצילים מוריים שכעסו על כך שהסולטאן אכל עם נוצרים וחששו שמא הוא התנצר.
לאחר שהשקט הושב, הורה אבו אל-חסן לבצר את גיברלטר. פרטים רבים על העיר החדשה של גיברלטר ידועים מעבודתו של הכרוניקאי המורי איבן מרזוק, "מוסנד" (נכתבה בשנים 1370–1371), המתארת את בנייתה מחדש של גיברלטר. העיר נתרחבה, חומות הגנה חדשות נבנו על מנת להגן מדרום וממערב ולהם נתווספו מגדלים ומעברים. גם הביצורים שכבר היו קיימים שופצו וחוזקו. הנקודות החלשות בגיברלטר אותן ניצלו הקסטיליאנים במתקפתם בוצרו גם הן.