De club werd in 1904 opgericht als Valletta United en won de landstitel in 1915 en 1932. Twee jaar later veranderde de club zijn naam in Valletta City en in 1939 in Valletta St. Paul's AFT. De huidige naam werd in 1944 aangenomen na een fusie met Valletta Prestons. Als Valletta FC was de club het succesvolste en won nog drieëntwintig titels.
In het seizoen 2009/10 waren de Nederlanders Ton Caanen (hoofdcoach), Jordi Cruijff (assistent-trainer/speler) en Geert den Ouden (speler) werkzaam bij Valletta.
Op 24 januari 2014 werd Jong Vitesse trainer André Paus aangesteld als nieuwe hoofdtrainer. Diezelfde dag werd ook Ted van Leeuwen, voormalig technisch directeur van Vitesse, aangesteld voor de functie als technisch directeur bij de Maltese club. Beiden zijn later in 2014 overgestapt naar Anorthosis Famagusta.[2][3]
Valletta, Malta
Zie Lijst van Europese wedstrijden van Valletta FC voor het hoofdartikel over dit onderwerp.
.svg){kind=small}
· 
· 