De club werd in 2005 opgericht als FK Policija Vilnius. In 2008 werd de naam FK REO LT Vilnius aangenomen. De club begon op het vierde niveau in de regionale poule rond Vilnius waar tweemaal een eerste en tweemaal een tweede plaats behaald werd. REO weigerde in 2008 promotie. In 2010 kwam de club voor het eerste op het derde niveau uit en werd meteen kampioen. In 2011 gebeurde hetzelfde op het tweede niveau waardoor REO Vilnius in 2012 voor het eerst in de A Lyga zal spelen. De club nam hierna de naam FK Vilnius aan, maar moest deze van de bond snel terugdraaien omdat er eerder al een club (FC Vilnius) onder die naam gespeeld had. Ook een poging om de club Žalgiris te noemen, werd niet toegestaan omdat die naam bij de huidige club VMFD Žalgiris hoort. Ook mocht de naam niet afwijken van het vorige seizoen. In juli 2012 werd het team vanwege financiële problemen uit de competitie genomen en de overige wedstrijden werden een 0-3 forfaitnederlaag.
