Vilniaus "Sakalai", 1994 m. dar žaidę, "Lietuvos Policijos Akademijos" pavadinimu, laimėjo LKF aukščiausios lygos (dabar LKAL) pirmenybes. Tais pačiais metais, kartu su Šiaulių "Kelininku" buvo priimti į LKL.
1995 debiutavo R.Koračo taurėje, kur antrame etape nusileido Atėnų "Panionios" (Graikija).
1998-1999 metų sezoną pradėjo susijungę su LKAL čempionais sostinės SK "Vadu".
1999 metais debiutavo kitame Europos turnyre – R.Saportos. Komandos vadovų keltas uždavinys buvo įvykdytas - pateko į 1/16, kur pralaimėjo Kroatijos "Splitui". Kitais metais toje pačioje taurėje pasitraukė po grupės varžybų.
"Sakalai" išaugino tokius rinktinės žaidėjus kaip Andrius Giedraitis ir Ramūnas Šiškauskas.
2006-2007 metų sezono viduryje klubą sukrėtė permainos - komandą paliko nuo jos įkūrimo dirbęs treneris Linas Šalkus, o prie ekipos vairo stojo legendinis Lietuvos krepšininkas Rimas Kurtinaitis.

Pasiekimai LKL:

1994-1995 m. 8 vieta
1995-1996 m. 5 vieta
1996-1997 m. 7 vieta
1997-1998 m. 4 vieta
1998-1999 m. 3 vieta
1999-2000 m. 4 vieta
2000-2001 m. 6 vieta
2001-2002 m. 6 vieta
2002-2003 m. 5 vieta
2003-2004 m. 4 vieta
2004-2005 m. 3 vieta reg. sezone, mažajame finale nusileido Šiaulių klubui
2005-2006 m. 5 vieta
2006-2007 m. 7 vieta