„Vėtros“ klubas Lietuvos futbole pasirodė 1996 m., kai nedideliame Rūdiškių miestelyje netoli Trakų susikūrė antrasis miestelio futbolo klubas ir 1996-1997 m. sezone debiutavo Vilniaus zonos A grupėje. Surinkusi panašiai taškų, kaip ir kitos vidutinio lygio komandos, Rūdiškių „Vėtra“ užėmė tik 10 vietą iš 12.

1997-1998 m. sezone prasidėjo komandos kilimas - Vilniaus zonoje užimta 2 vieta, iškovojant teisę žaisti trečio lygmens varžybose, kur Rytų zonoje 1998-1999 m. sezone užimta 4 vieta, o 1999 m. sezone Rūdiškių „Vėtra“ nė karto nepralaimėjusi tapo pereinamojo čempionato laimėtojais, 2000 m. sezone užtikrintai tapo LFF I lygos čempionais ir per stebėtinai trumpą laiką iškovojo teisę žaisti A lygoje.

Debiutui 2001 m. aukščiausioje lygoje Rūdiškių klubas kruopščiai ruošėsi, surado keletą veteranų, XX a. 9-10 dešimtmečiais žaidusių „Žalgiryje“ ir šiek tiek ragavusių rinktinės duonos. Taip komandoje atsidūrė į sezono vyriausių žaidėjų penketuką patekę Vladimiras Buzmakovas ir Ričardas Zdančius, taip pat 30-mečius jau atšventę Gintaras Rimkus bei Darius Spetyla. Pagal vidutinį amžių (beveik 28 metai) komanda buvo nepralenkiama, tačiau komandoje nežaidžiant jaunesniems nei 20 metų žaidėjams matyt pritrūko energijos. Sezono metu pasiekta rimtų pergalių (2:0 nugalėtas „Žalgiris“, du kartus įveiktas Panevėžio „Ekranas“), 2500 gyventojų turinčio Rūdiškių miestelio stadione lankėsi labai panašiai žmonių, kaip ir Vilniaus „Žalgirio“ stadione (abiejuose stadionuose vid. apie 400). Tačiau apatinėje lentelės pusėje konkurencija buvo per didelė (6 nuo 10 vietos skyrė tik 6 taškai), o ir įvarčiais komanda žiūrovų nelepino (32 įvarčiai per 36 rungtynes - mažiausiai lygoje), taigi priešpaskutinę vietą užėmusi „Vėtra“ grįžo į I lygą.

2002 m. LFF I lygos sezone „Vėtra“ vėl užtikrintai iškovojo čempionų vardą, per 30 rungtynių pelnydami 131 įvartį, praleidę tik dvylika, tik kartą pralaimėję.

2003 m. A lygos sezone komandos branduolį ir vėl sudarė patyrę žaidėjai (Rolandas Vaineikis, Gintaras Rimkus, Marius Poškus, Ramūnas Stonkus, Vytautas Karvelis, Gediminas Kontautas), o komandos amžiaus vidurkis buvo dar šiek tiek didesnis nei 2001 m. (27,72 metų). Komandą iki metų vidurio treniravo Vytautas Jančiauskas, antroje metų pusėje dirbo laikinuoju treneriu paskirtas Valdas Urbonas, kuriam padėjo Valdas Ivanauskas. Nežinia ar pasiteisino vyresnio amžiaus žaidėjų taktika, ar padėjo gabūs treneriai, bet ką tik iš I lygos pakilusi komanda užtikrintai užėmė 3 vietą, net 13 taškų pralenkdami 4 vietoje likusį Vilniaus „Žalgirio“ klubą. 2002-2003 m. LFF taurėje klubo komanda pirmą kartą pasiekė finalą, kur nusileido Klaipėdos „Atlantui“. Beje, 2003 m. sezone Rūdiškių stadione vidutiniškai lankėsi net po 800 žiūrovų.

Iškovojęs bronzos medalius, 2004 m. „Vėtros“ klubas persikraustė į Vilnių, kur vasarą pradėjo žaisti modernizuotame „Lokomotyvo“ stadione. Metų pradžioje vyr. treneriu paskirtas Valdas Ivanauskas, sezonui įpusėjus jį pakeitė Sigitas Aliubavičius. Orientuojantis į patyrusius žaidėjus (prie veteranų prisidėjo Aidas Preikšaitis), komandos amžiaus vidurkis vidutiniškai jau buvo 28,2 metų (beveik 2 metais daugiau už antroje vietoje pagal amžių likusią Kauno FBK komandą), rezultatai prastėjo - 2004 m. užimta tik 5 vieta, į priekį praleidžiant „Atlantą“ ir „Žalgirį“. Persikėlus į Vilnių bei suprastėjus rezultatams, klubo namų rungtynėse lankėsi žymiai mažiau žiūrovų nei kituose stadionuose (vid. 340). Tačiau buvo ir teigiamų pokyčių - startinėje sudėtyje įsitvirtino nuo 2002 m. į „Vėtrą“ perėjęs dvidešimtmetis Darvydas Šernas.

2004 m. klubas pirmą kartą dalyvavo Europinėse varžybose - Intertoto taurėje, kur pirmam etape įveikė Narvos „Trans“, antrajame etape Edinburge sužaidė lygiosiomis su Edinburgo „Hibernians“, o namuose minimaliu rezultatu įveikė šią komandą ir tik trečiajame etape „Vėtrą“ eliminavo danų Esbjergo FB klubo komanda.

2005 m. sezone „Vėtros“ komandos amžiaus vidurkis vis dar buvo didžiausias lygoje, tačiau komanda atjaunėjo iki vid. 27,4 metų. Šį sezoną komandą į ketvirtą vietą vedė pusę metų vyr. treneriu dirbęs Sergej Borovski, taip pat pagrindiniai žaidėjai - Julius Raliukonis, Žilvinas Žudys, Igoris Steško, Aidas Preikšaitis, Andrius Kochanauskas, Gediminas Butrimavičius, Nerijus Sasnauskas ir kiti. Iki antrųjų bronzos medalių pritrūko tik 2 taškų. Gerai sekėsi ir 2005 m. LFF taurėje - antrą kartą pasiektas finalas, šį kartą laimėti taurę sutrukdė Kauno FBK. Intertoto taurėje 2005 m. sekėsi prasčiau - jau pirmame etape „Vėtrą“ eliminavo Klužo „Ecomax“. Dar suprastėjo ir stadiono lankomumas - vidutiniškai rungtynėse lankėsi tik 255 žiūrovai.

2006 m. pirma sezono pusė nebuvo labai sėkminga, tačiau sezono viduryje atėjus rusų treneriui Aleksandr Tarchanov rezultatai pagerėjo ir antrą kartą iškovoti bronzos medaliai. Šį sezoną legionierius iš Rusijos Serguei Kouznetsov tapo rezultatyviausiu lygos žaidėju, įmušdamas 18 įvarčių. Komandą papildė Algis Jankauskas, Egidijus Juška, Donatas Vencevičius, Rolandas Karčemarskas. Jau ketvirtą sezoną iš eilės „Vėtra“ pirmavo lygoje pagal vidutinį žaidėjų amžių, net trys iš keturių vyriausių lygos žaidėjų žaidė „Vėtroje“ (Rolandas Vaineikis, Aidas Preikšaitis, Vaidas Žutautas), tačiau atotrūkis nuo kitų komandų mažėjo (vid 27 metai). A lygoje „Vėtros“ stadiono lankomumas ženkliai padidėjo (iki vid. 643 žiūrovų). Intertoto taurėje ir vėl nepavyko peržengti pirmojo etapo - abejose rungtynėse teko pripažinti Šelburno SC komandos pranašumą.

2007 m. pradžioje komandą treniravusį A. Tarchanov vėliau pakeitė iki tol metus komandoje žaidęs Donatas Vencevičius, kuriam nepavyko su komanda iškovoti dar vieno medalių komplekto - surinkusi tiek pat taškų kai ir pernai, šį kartą „Vėtra“ liko 5 vietoje. Komandos žaidėjų amžiaus vidurkis (25,5 m.) pirmą kartą nebuvo didžiausias lygoje. Daugiausiai 2007 m. žaidė Gediminas Butrimavičius, Marijan Budimir, Egidijus Juška, Algis Jankauskas, ilgametis rinktinės žaidėjas Andrius Skerla, taip pat nemažai legionierių (Pedro Botelho, Bobi Božinovski, Dejan Milošeski, Stanislav Kozyrev, Severino Lima De Moura, Gjoko Cvetanovski, Andrej Usačiov, Denis Malinin, Vachtang Kvaratskhelia ir kiti). Stadiono lankomumas pakito nežymiai (A lygoje vid. 622 žiūrovai per rungtynes). Intertoto taurės pirmame etape Vilniaus komanda nugalėjo Lanelio AFC (Velsas), antrame etape keistai susiklosčius aplinkybėms įveikta Varšuvos „Legia“ (po lenkų sukeltų riaušių antrosios rungtynės nevyko), o trečiame etape bendru rezultatu 0:6 nusileista Blakberno „Rovers“.

2008 m. sausio mėnesį prie „Vėtros“ vairo stojo patyręs treneris Virginijus Liubšys ir komanda vėl iškovojo bronzos medalius, tiesa nelabai užtikrintai. Komanda ne tik trečią kartą iškovojo bronzą, bet ir trečią kartą pateko į LFF taurės finalą, kur ir vėl nusileido Kauno FBK. Dar šiek tiek atjaunėjusios komandos branduolys - Gediminas Butrimavičius, Tadas Kijanskas, Algis Jankauskas, Valdemar Borovskij, Marius Kazlauskas, Gediminas Butavičius, Anatolie Ostap, Evaldas Grigaitis. Iš gausaus sezoną pradėjusių legionierių būrio (Roman Smiško, Gjoko Cvetanovski, Dejan Milošeski, Viačeslav Sofroni, Aleksandar Toleski) metų gale liko tik G. Cvetanovski ir M. Andraščik. 2008 m. „Vėtra“ debiutavo ir UEFA taurėje, kur susitiko su Stavangerio „Viking“, kuriuos namuose po kurioziško įvarčio įveikė, tačiau į kitą etapą nepateko.

2009 m. „Vėtra“ atjaunėjo dar labiau (vid. 24 metai), tačiau iki paskutinių turų kovojo dėl pirmosios vietos ir pirmą kartą klubo istorijoje pasipuošė sidabro medaliais. Antrą kartą UEFA taurėje dalyvavusi komanda taip pat pasirodė garbingai - pirmame atrankiniame etape įveiktas Grėvenmacherio CS klubas, antrajame net po pralaimėjimo namuose sugebėjo įveikti Helsinkio HJK, ir tik trečiame etape neprilygo vienos stipriausių pasaulyje Anglijos Premier lygos tais metais 7-ąją vietą užėmusiai Londono „Fullham“ komandai. Deja 2009 m. metai pažymėti ne tik didžiausiomis klubo pergalėmis, bet ir pasiektu kritiniu finansinio nuosmukio tašku.

2010 m. "Vėtros" prezidento kėdę iš Romo Stašausko perėme verslininkas iš Rusijos A.Treušnikovas, kuris pažadėjo užglaistyti nuo 2009-ųjų besitęsusius įsiskolinimus žaidėjams ir administracijai. Komandos sudėtis iš esmės nepakito, deja į kitus klubus patraukė svarbūs "Vėtros" žaidėjai patyręs gynėjas Tadas Kijanskas ir jaunas bei perspektyvus puolėjas Evaldas Grigaitis, taip pat komandą paliko ir patyręs žaidėjas Tomas Mikuckis. Dar viena nemaloni naujiena klubą užklupo įsibėgėjus sezonui - klubui atimta teisė žaisti UEFA Europos lygos turnyro atrankinėse varžybose. UEFA teigimu "Vėtra" negali žaisti dėl negautos A lygos licencijos (dėl nelaiku įvykdytų finansinių įsipareigojimų 2010m. sezone "Vėtrai" A lygoje leista žaisti tik išimties tvarka bei su -6 taškų sezono starto deficitu).