XX a. 10-ajame dešimtmetyje pirmosios Lietuvos futbolo lygose žaidė keletas futbolo komandų, kurios gana dažnai keisdavo pavadinimus, kai kuriose daugumą žaidėjų sudarė lenkai. Kartais „Polonijos“ pirmtakais laikomi Geležinis Vilkas Vilnius, Žalgiris-2 Vilnius ir Lokomotyvas Vilnius, tačiau šie klubai turi atskirą istoriją, nepaisant to, kad kai kuriais laikotarpiais jų komandose žaidė nemažai lenkų. 1993–1994 m. „Polonija“ buvo prisijungusi prie Andas Vilnius komandos.
Stipriausia „Polonija“ buvo tarp 1996 ir 2005 metų, kai žaidė aukščiausiuose šalies divizionuose. 1999 m. rudenį pagrindinė komanda vadinosi „Ardena“, o dukterinė – „Polonija“. Nuo 2006 m. komanda ėmė žaisti III lygos Vilniaus zonoje, o 2011 m. pakilo į II lygą, nors prieš tai ir nebuvo laimėjusi Vilniaus pirmenybių.
Pastaba: neįskaitomi 1924–1930, 1935, 1942–1943, 1945 m. sezonai, kai nebuvo vientisos lygos, taip pat 1939–1940, 1941, 1943–1944 m. nebaigtos pirmenybės.