Klub powstał w 1928 r. z inicjatywy Koła Związku Młodzieży Wiejskiej "Wici". Jego założycielami byli: Edward Krzywdziak, Władysław Czarkowski, Adam Czoła, Marian Bromurski oraz Jan Basista.
W drugiej połowie 1928 r. w Klubie powstała sekcja piłki nożnej. Drużyna przyjęła nazwę "Orlątka". W 1932 r. w Klubie działały też sekcje: lekkoatletyczna, kolarska i kulturalno-oświatowa. Początkowo Klub nie posiadał własnego boiska, w związku z tym zawody sportowe odbywały się na przystosowanych do tego celu pastwiskach w Kobierzynie.
W 1933 r. klubowa drużyna piłkarska została zgłoszona do Związku Piłkarskiego i od tego momentu rozpoczęła rozgrywać mecze ligowe. Rok później powstało boisko sportowe przy obecnej ul Skośnej, obok cmentarza Lubostroń. Boisko wybudowali w czynie społecznym zawodnicy, działacze oraz sympatycy Klubu. Oficjalne otwarcie, połączone z poświęceniem i oddaniem obiektu do użytku, nastąpiło w 1934 r. Na ówczesne czasy była to bardzo poważna inicjatywa, tym bardziej, że Klub utrzymywał się wyłącznie ze składek członkowskich oraz wpływów uzyskanych ze sprzedaży biletów. W 1938 r. Klub zaczął osiągać pierwsze sukcesy - sekcja piłkarska zajęła II miejsce w klasie B. Ówczesny Zarząd Klubu miał pomysł na dalszy rozwój i poprawę wyników sportowych, niestety przeszkodą był wybuch II Wojny Światowej. W okresie okupacji "Victoria" oficjalnie zawiesiła swoją działalność, udało się jednak rozegrać potajemnie kilka meczy z drużynami sąsiednich Łagiewnik, Borku Fałęckiego i Ludwinowa.
Po wyzwoleniu, w drugiej połowie 1945 r., przedwojenni działacze: Franciszek Kuś, Jan Basista, Wojciech Kloc, Władysław Białek oraz zawodnicy Marian Mądry i Jerzy Skóra, starali się wskrzesić dawny poziom organizacyjny i sportowy Klubu. Zrodziły się nowe pomysły i inicjatywy. Najważniejszą z nich było porozumienie Zarządu Klubu z Dyrekcją Szpitala Psychiatrycznego im. dr J. Babińskiego w Kobierzynie w sprawie budowy na terenie szpitala nowego obiektu sportowego. Wszelkie prace udało się zakończyć w 1953 r. W tym okresie prezesem Klubu był dr Władysław Salawa. Drużyna piłkarska, reprezentując służbę zdrowia, zdobyła wówczas I miejsce w rozgrywkach o Puchar Polski.
W 1955 r. piłkarze "Victorii" wywalczyli awans do klasy A, w której przyszło im rozgrywać mecze z drużynami "Hejnału" Kęty, "Victorii" Jaworzno, "Kalwarianki", "Borku" oraz "Tymbarku". Na szczególną uwagę zasłużyli: Ryszard Nowak - najlepszy bramkarz w historii Klubu (został zakupiony przez KS "Chełmek" za 11 par butów) oraz Zbigniew Czop - pomocnik, grający później w pierwszoligowym "ŁKS".
Rok 1966 był rokiem kryzysu. Przełamał go, wybrany w 1967 r. prezes Klubu, Franciszek Janik. Udało mu się stworzyć 3 drużyny grające w klasach A, B i juniorów. Łącznie w Klubie zrzeszonych było siedemdziesięciu zawodników. W 1968 r. pierwsza drużyna spadła do klasy B. Było to bezpośrednio związane z przedwczesną śmiercią prezesa Franciszka Janika. W 1983 r. funkcję prezesa Klubu objął były zawodnik Adam Suwaj. Klub stał nad przepaścią. Gdyby nie pomoc ze strony dyrekcji Szpitala oraz zapalonych działaczy, Klub zniknąłby z mapy sportowej Krakowa. Pomoc dr Zdzisława Wasieczki oraz Związków Zawodowych Szpitala pozwoliła ponownie szkolić młodzież w Klubie. Forma drużyny ustabilizowała się, co uwidoczniły rozgrywki ligowe. W latach 1995-98 prezesem Klubu został Tadeusz Zaraska, który pełnił tę funkcję do 1999 r.
W 1999 r. prezesem Klubu został Krystian Basista. W lipcu 1999 r. nastąpiło połączenie dwóch klubów: "Victoria" i "Krak Gamma". Powstała nowa nazwa Klubu "Victoria Krak Gamma". Nowy zespół rozpoczął rozgrywki w krakowskiej A klasie grupie II. W klubie powstała sekcja juniorów oraz oldboi. Fuzja dwóch klubów trwała krótko. W 2004 r. klub powrócił do starej nazwy KS VICTORIA. W roku 2007 odbyły się nowe wybory, gdzie jednogłośnie wybrano na prezesa Klubu Krystiana Basistę. Powstał nowy zarząd, który rozpoczął etap zmian w klubie. Został uchwalony nowy statut klubu oraz zmieniony regulamin.
W roku 2008 Klub otrzymał statut Organizacji Pożytku Publicznego. Sezon 2009/10 Klub rozpoczął z nowymi planami i pomysłami na przyszłość. Obecnie w Klubie znajdują się sekcje: Senior " B" klasa, Senior "C" klasa, Junior Starszy II liga, Oldboi II liga.
