Gibraltar ansökte om Uefa-medlemskap första gången 1999 och fick nej senast i januari 2007. Fallet har flera gånger tagits upp i Idrottens skiljedomstol som har fastslagit varje gång att Gibraltar måste tillåtas medlemskap. Den 1 oktober 2012 blev Gibraltar provisorisk Uefa-medlem.[2]
Efter omröstning på Uefas kongress i London den 24 maj 2013 blev Gibraltar till slut accepterat som fullvärdig medlem i Uefa. Bara två länder, Spanien och Vitryssland, röstade emot.[3] Den 29 mars 2015 gjorde Gibraltars herrlandslag sitt första mål i en tävlingsmatch i fotboll i en EM-kvalförlust mot Skottland.[4] Även Fifa vägrade Gibraltar medlemskap, men ändrade sig efter en dom i idrottens skiljedomstol från 2 maj 2016. Sedan 13 maj 2016 är Gibraltar medlem i Fifa som medlem nummer 211. Därmed får landslaget i framtiden även kvalspela till VM-turneringarna.
Gibraltar spelade sitt första VM kval i grupp H. Det blev svåra motstånd och man kom, likt EM kvalet 2016, sist i gruppen utan poäng. Gibraltar var dock nära att få ett poäng mot Cypern hemma i matchdag 6. Cypern hade 1–0 i 10:e matchminuten då Gibraltiske spelaren Roy Chipolina gjorde självmål i 10:e matchminuten. Gibraltar lyckades kvittera i 30:e matchminuten. Det såg ut som att Gibraltar skulle ta en pinne mot Cypern. Men detta blev inte fallet då Cypern, via Pieros Sotiriou gjorde mål i 87:e matchminuten och Cypern vann med 2–1. Gibraltar lyckades få in tre mål i hela kvalet. Bland annat mot Grekland där Gibraltars mål tog landet till kvittering innan Grekland lyckades göra ytterligare tre mål i första halvlek. Det blev även mål borta mot Cypern.
Under Uefa Nations League 2018/2019 tog Gibraltar två segrar totalt. Den första kom mot Armenien borta den 13 oktober 2018 då försvararen Joseph Chipolina gjorde mål i femtionde minuten med en straff. Armenien lyckades inte besegra Gibraltar och matchen blev Gibraltars första vinst i en Uefa-tävlingsmatch. Detta följdes upp av vinst på hemmaplan mot Liechtenstein med resultatet 2–1 till Gibraltar.
I Kvalet till EM 2020 hamnade man i sällskap med Schweiz, Danmark, Irland och Georgien. Gibraltar fick inte fram några poäng i kvalspelet. Man åstadkom två mål i en hemmamatch mot Georgien som man förlorade med resultatet 2–3 till Georgien.