Klub został założony w 1999 roku. Pierwszym prezesem był Pan Zenon Leńczyk. W pierwszym sezonie UKS Dukla występuje w rozgrywkach klasy okręgowej seniorów oraz w klasie "A". Na pierwsze sukcesy nie trzeba było długo czekać w 2000 roku juniorzy : Tomasz Leńczyk, Tomasz Kozubal, Piotr Piróg, Łukasz Stasiak awansowali do Półfinałow Drużynowych Mistrzostw Polski W tym samym roku drużyna składająca się z wychowanków klubu awansowała do III LIGI !!! Miłą niespodziankę sprawiła także druga drużyna UKS Dukla, która zdobywając mistrzostwo klasy A, awansowała do ligi okręgowej. W Olkuszu odbyły się Półfinały Mistrzostw Polski. W pierwszym meczu zawodnicy UKS-u wygrali 4-2 z MKS "Jedynka" Łódz. W drugim meczu nasza drużyna przegrała z faworytami turnieju 4-0 z KSP "Pogórze" Kraków. W rezultacie zajęli 5-8 miejsce. Klub w lipcu 2000 roku zorganizował loterie fantową.Główną nagrodą był rower górski. W sierpniu 2000 r. Zarząd UKS TKKF "Dukla" w nagrodę za awans do III Ligi i znakomista postawa na Półfinałach Mistrzostw Polski ufundował tygodniowy wypoczynek w Hajduszoboszlo. W wrześniu 2000 roku klub pozyskuje utalentowanego juniora Bogdana Maciejewskiego. Druga drużyna UKS "Dukla" w pierwszym sezonie występów w klasie okręgowej zajęli 2 miejsce. Miejsce to dało szanse na gre w barażu o III Lige. Jednak zespół z Sanoka był poza zasięgiem. Drugi raz pod rząd drużyna juniorów w składzie: Bogdan Maciejewski, Tomasz Kozubal, Łukasz Stasiak awansowała do Półfinałow Mitrzostw Polski. Zawody odbyły się w Łodzi. Nasi zawodnicy zajęli 9 miejsce. Po raz drugi zawodnicy za osiągnięcia wyjechali na Węgry. Natomiast dla najmłodszych wybijających sie zawodników postanowiono wysłać ich na dwu tygodniowy obóz do Leska. W sezonie 2001/2002 Marcin Kozubal na II WTK zajął II miejsce. W seonie 2001/2002 zawodnicy zajęli 10 miejsce w III Lidze. Zawodnicy z klasy okręgowej zdobyli 5 miejsce.