Klubas įsikūrė sovietmečiu prie P. Eidukevičiaus avalynės kombinato, kuris įkurtas 1949 m. Klubas žaidė ledo ritulio čempionate, praktikavo futbolą. 1952 m. P. Eidukevičiaus odos galanterijos ir avalynės kombinato futbolo komanda pasiekė „Tiesos“ taurės pusfinalį. 1956 m. pasivadino „Raudonąja žvaigžde“,[1] priklausė „Žalgirio“ sporto draugijai.[2]1959 m. prie kombinato buvo prijungtas vaikiškos avalynės fabrikas „Viktorija“. 1959 m. „Raudonoji žvaigždė“ laimėjo LTSR futbolo lygos aukso medalius, kai komandoje žaidė nemažai buvusių „Spartako“ meistrų komandos žaidėjų. 1962 m. komanda nusilpo, kadangi neugdė naujos pamainos – vasarą komanda atsisakė žaisti „Tiesos“ turnyre, netrukus paliko ir LTSR čempionatą. Apie 1970 m. persivadino „Batu“, atgavus Nepriklausomybę 1998 m. komanda laimėjo Vilniaus pirmenybes, tačiau 1999 m. iširo.
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.
