Kiedyś w Stalowej Woli liczyła się tylko Stal. Piłkarze i koszykarze występowali w ekstraklasie, pięściarzem silnej sekcji bokserskiej był Lucjan Trela, który na igrzyskach olimpijskich w Meksyku walczył z George Foremanem, późniejszym zawodowym mistrzem świata. Miała też Stal mocnych lekkoatletów - olimpijkę z Barcelony Genowefę Patlę (z domu Olejarz), maratończyka uczestniczka igrzysk w Barcelonie i Atlancie Leszka Bebłę.
Zmiana ustroju nie przysłużyła się klubowi podobnie jak całemu regionowi. Sportowa Stal pozbawiona dotacji od dotychczasowego sponsora-miejscowej huty – rdzewiała. Większość środków z tego, co zostało w skromnym budżecie, przekazywana była na piłkarzy. Inne sekcje nie miały szans na przeżycie. Padały. Trenerzy i działacze lekkoatletyczni nie dali za wygraną. Zabrali ze Stali zawodników i w 1998 roku założyli nowy klub – Victoria.
Od parafiady do olimpiady
Na stronie internetowej pod nazwą klubu widnieje dopisek „przy Bazylice Matki Bożej Królowej Polski w Stalowej Woli". To z wdzięczności. Proboszcz parafii Edward Madej pomagał przy narodzinach Viktorii, znalazł się zatem wśród członków pierwszego honorowego zarządu. Ale to tylko jeden z powodów religijnej tytulatury. Założyciel klubu Stanisław Anioł, ratując stalowolską lekkoatletykę poprosił o pomoc kolegę ze Starachowic, który również stworzył klub przy parafii, działający w oparciu o wartości chrześcijańskie. Udostępnił statut. Zmieniono w nim tylko nazwę i miejsce klubu. KKS Victoria Stalowa Wola mogła działać.
Klub do dziś mocno trzyma się swoich katolickich korzeni. W statucie jest zapisane „wychowywanie dzieci, młodzieży i dorosłych poprzez kulturę fizyczną, sport, turystykę i rekreację w oparciu o zasady etyki katolickiej". Na zgrupowaniach jest czas na trening, ale i na niedzielną mszę. Lekkoatleci ze Stalowej regularnie uczestniczą w parafiadach, ogólnopolskich zawodach organizowanych co roku w Warszawie z mottem „od parafiady do olimpiady". W klasyfikacji klubowej zawodów lekkoatletycznych już kilkakrotnie zajmowali na tych zawodach pierwsze miejsce.
- Miałem jeszcze wtedy taki pomysł, żeby Victoria w każdej parafii miała jedną sekcję – opowiada o początkach Stanisław Anioł. Została lekkoatletyka, są jeszcze szachy, ale to wystarczy. Pracy dość, sukcesów też całkiem sporo.