La storia della Nazionale di Gibilterra ebbe inizio nell’aprile 1923, quando la squadra disputò due partite amichevoli contro il Siviglia, perdendole entrambe. Nel 1949 pareggiò un’amichevole contro il Real Madrid. Prima del riconoscimento internazionale, la selezione prese parte a numerose competizioni non ufficiali per nazionali: la prima a cui prese parte furono gli Island Games del 1993, benché Gibilterra non sia un’isola. In tale occasione disputò la sua prima partita contro una squadra nazionale, Jersey, che terminò con una sconfitta per 1-2. La migliore vittoria non ufficiale di Gibilterra è la partita vinta per 19-0 contro Sark a Saint Martin (Guernsey), mentre la peggiore sconfitta non ufficiale è la partita persa per 0-5 contro la Groenlandia a Freshwater, nell’Isola di Wight. Nel 2007 si aggiudicò gli Island Games. La Federazione calcistica di Gibilterra presentò per la prima volta domanda di affiliazione alla UEFA nel 1999, ma la domanda fu respinta a causa della forte opposizione della Federazione spagnola, che derivava non solo dalla rivendicazione di Gibilterra da parte della Spagna, ma anche dal timore del governo spagnolo che l’accettazione di Gibilterra potesse costituire un precedente che avrebbe potuto spingere anche le federazioni basca e catalana a presentare domanda di adesione alla UEFA. La Federazione gibilterriana adì allora il Tribunale Arbitrale dello Sport di Losanna nel 2006: il TAS ordinò alla UEFA di procedere all’affiliazione, ma, nonostante la vincolatività delle decisioni del TAS, solo tre Paesi membri (Inghilterra, Scozia e Galles) votarono a favore dell’ammissione in occasione del congresso della UEFA che si tenne il 27 gennaio 2007 a Düsseldorf, dopo che la federazione spagnola aveva minacciato di ritirare le squadre spagnole da tutte le competizioni UEFA per club. In seguito alle pressioni della Federazione spagnola, la UEFA stabilì poi nuove regole per l’affiliazione, che limitano l’appartenenza alla UEFA a Stati sovrani riconosciuti come tali dalle Nazioni Unite.
La Federazione gibilterriana adì allora nuovamente il Tribunale Arbitrale dello Sport di Losanna nel 2011: il TAS ordinò di nuovo alla UEFA di affiliare la Federazione calcistica di Gibilterra, statuendo che dovesse farsi applicazione delle vecchie regole sull’affiliazione, dal momento che la prima domanda di ammissione fu presentata dalla GFA nel 1999, ben prima dell’entrata in vigore delle nuove regole. Il 1º ottobre 2012 la UEFA ottemperò infine alla decisione del TAS, ammettendo così Gibilterra come membro provvisorio. La Federazione di Gibilterra ottenne l’affiliazione definitiva al Congresso della UEFA tenutosi il 24 maggio 2013 a Londra, con i soli voti contrari di Spagna e Bielorussia: da tale data Gibilterra è membro UEFA di pieno diritto. La nazionale poté così partecipare alle qualificazioni al Campionato europeo del 2016, oltre che alle competizioni UEFA per le nazionali giovanili. Gibilterra fece il suo esordio ufficiale il 19 novembre 2013, quando pareggiò in amichevole contro la Slovacchia 0 a 0. Il 26 maggio 2014 pareggiò in amichevole 1-1 a Tallinn contro l’Estonia, con gol di Jake Gosling. Il 4 giugno 2014 ottenne la prima vittoria della sua storia, battendo in amichevole Malta per 1-0 con gol di Kyle Casciaro. Il 7 settembre 2014 esordì in competizioni ufficiali in occasione della prima partita di qualificazione agli Europei del 2016 contro la Polonia, disputata in campo neutro, presso l’Estádio Algarve di Faro (Portogallo), dal momento che il Victoria Stadium di Gibilterra, non soddisfacendo i requisiti dell’UEFA per le competizioni ufficiali per nazionali, può ospitare solamente partite amichevoli. La partita terminò con una sconfitta per 0-7.
Il 2 marzo 2015 l’allenatore Allen Bula venne esonerato dopo aver perso le prime 4 partite del girone di qualificazione, con 21 gol subiti e 0 gol fatti. Venne sostituito ad interim da David Wilson, che guidò la nazionale nella partita disputata il 29 marzo 2015 allo stadio Hampden Park di Glasgow contro la Scozia, persa 6-1; in tale occasione Lee Casciaro segnò il primo gol in competizioni ufficiali per Gibilterra (quello del momentaneo 1-1). Nel luglio 2015 l’inglese Jeff Wood divenne il nuovo commissario tecnico. Sotto la sua gestione la nazionale segnò con Jake Gosling il suo secondo ed ultimo gol nelle qualificazioni ad Euro 2016 nella partita persa 8-1 contro la Polonia. Gibilterra terminò il girone con 10 sconfitte, 2 reti fatte e 56 subite. Il 2 maggio 2016 il TAS intimò alla FIFA di dare il via a tutte le azioni necessarie per ammettere Gibilterra come membro con pieno diritto. Il 13 maggio 2016 la Gibraltar Football Association ottenne così l’affiliazione alla FIFA con 172 voti a favore e 12 contrari, diventando la 211ª federazione affiliata, immediatamente dopo la Federazione kosovara. Gibilterra poté quindi partecipare alle qualificazioni al Campionato mondiale del 2018.