Na początku był pomysł braci Miksztalów. W przebrnięciu przez sprawy papierkowe pomógł bardzo Marian Kuczaj, ówczesny szef Kolegium Sędziów NOZPN, dyrektor Zespołu Szkół w Starym Sączu, w którym pracował Tomasz Miksztal. Propozycji na nazwę klubu było sporo. Zwyciężyła Galicja -  Sylwii Miksztal (żony Pawła).

Zebranie założycielskie Klubu Sportowego Galicja Nowy Sącz odbyło się 1 czerwca 1994 roku. Na liście założycieli złożonej w Wydziale Infrastruktury Społecznej Urzędu Wojewódzkiego w Nowym Sączu było 15 osób: Sławomir Raczek, Paweł Miksztal, Tomasz Miksztal, Tomasz Błaszczyk, Przemysław Dąbrowski, Rafał Ciastoń, Lesław Augustynowicz, Marian Gizicki, Wojciech Żelasko, Maciej Dańczak, Krzysztof Dańczak, Sylwia Miksztal, Przemysław Machowicz, Przemysław Piotrowski i Tomasz Krogulski.

Zgodnie z zarejestrowanym statutem celem klubu jest:
1. rozwój różnych dyscyplin sportu oraz stałe podnoszenie jego poziomu,
2. organizowanie działalności sportowej ze szczególnym uwzględnieniem funkcji zdrowotnych,
3. uczestniczenie w imprezach sportowych organizowanych na obszarze działania samorządu terytorialnego i poza nim,
4. kształtowanie pozytywnych cech charakteru i osobowości poprzez uczestnictwo w realizacji zadań sportowych Klubu,
5. czynny udział w życiu kulturalnym, gospodarczym i społeczno-politycznym.

22 czerwca 1994 roku KS Galicja został wpisany do rejestru stowarzyszeń kultury fizycznej i ich związków Wydziału Turystyki i Kultury Urzędu Wojewódzkiego w Nowym Sączu nr 129.

9 lipca 2001 roku zostaliśmy wpisani pzez Sąd Rejonowy w Krakowie do „Rejestru stowarzyszeń, innych organizacji społecznych i zawodowych, fundacji i publicznych zakładów opieki zdrowotnej” jako stowarzyszenie kultury fizycznej pod numerem KRS 0000021821.

Istniejemy mimo wielu przeciwieństw: notorycznego braku pieniędzy, sprzętu i boiska. Korzystaliśmy z gościnności Jedności, Zawady, Dunajca, Świniarska, Brzeznej i Zabełcza, gdzie rozgrywaliśmy mecze w roli gospodarza, a nawet przez dwie rundy rozgrywaliśmy wszystkie mecze na wyjazdach. Bywało tak, że nie byliśmy w stanie zebrać na mecz 11 zawodników i 90 minut graliśmy w osłabieniu. Ogłoszenie o tym, że poszukujemy zawodników pojawiło się nawet w sądeckiej prasie!  Bywało tak, że nie trenowaliśmy i spotykaliśmy się tylko na meczach. Nadal jest tak, że jeździmy na spotkania własnymi samochodami i wspomagamy budżet klubu własnymi pieniędzmi. Naszym największym sponsorem jest Urząd Miasta w Nowym Sączu.    

Zaczynaliśmy w klasie C. Byliśmy dostarczycielem punktów. W debiutanckim sezonie zajęliśmy ostatnie miejsce. Pierwsze punkty zdobyliśmy dopiero w rundzie rewanżowej. Po dwóch sezonach, dzięki reorganizacji awansowaliśmy do klasy B.

Drugi raz gramy w klasie A (debiutowaliśmy w tej klasie w sezonie 2006/07) i obok meczu z Sandecją Nowy Sącz w Pucharze Polski (1997) oraz udziału w trzeciej rundzie PP na szczeblu okręgu (w 2004 roku) to nasz największy sukces.

Mieliśmy nawet zespół trampkarzy, który zajął 2 miejsce w powiecie ustępując tylko Dunajcowi. Pierwszym prezesem był lekarz Wacław Szczypuła, następnym Tomasz Miksztal. Trenował nas były piłkarz Pogoni Szczecin i Sandecji Jan Wojciechowski. Grał z nami były zawodnik Korony Kielce Adam Jesiąka.