Nagy-Britannia gyarmataként korán bekapcsolódott a sportág eseményeibe. A labdarúgó-szövetség 1959-ig Londonhoz tartozott. Az afrikai szekcióban beneveztek az 1960-as olimpiai selejtezőkbe, de nem jártak sikerrel. Rendszeresen részt vesznek a VB és Eb selejtezőkön, de eddig nem jutottak eredményre. Az első két győzelmüket tétmérkőzésen 1975-ben és 1982-ben érték el Görögország és Izland ellen. A következő győzelemre 1993-ig kellett várni, ekkor Észtországot verték meg.
Málta válogatottja tehát bármikor képes meglepetés eredményeket elérni. Ilyenek voltak 2005-ben: a Horvátország és Bulgária és Észak-Írország elleni 1–1. A 2006-os labdarúgó-világbajnokság előtt nem sokkal Németországban Japánt győzték le barátságos mérkőzésen 1–0-ra. 2006. október 11-én Magyarországot győzték le 2–1-re Európa-bajnoki selejtezőben André Schembri két góljával. 2007. február 7-én a 2008-as labdarúgó-Európa-bajnokság egyik házigazdájával Ausztriával játszott 1–1-es döntetlent. Ez a mérkőzést az ötvenedik évfordulója volt az első nemzetközi találkozójuknak. 2007. szeptember 8-án Törökország ellen 2–2-re végzett Eb-selejtezőn.
A valaha volt legnagyobb arányú győzelmüket 2008. március 26-án érték el, amikor Liechtensteint fektették két vállra. A vége 7–1 lett Málta javára, Michael Mifsud ötször talált be. 2009. szeptember 9-én kis híján nagy bravúrt hajtottak végre, ugyanis Svédország ellen nem sokkal a befejezés előtt 0–0-ra álltak, azonban a vége 1–0 egy öngóllal a svédek javára.
