W lipcu 1996 podpisano umowę, na mocy której nastąpiło połączenie sekcji piłki nożnej klubu AZS AWF z Podlasiem, tworząc zespół o nazwie AZS-Podlasie Biała Podlaska. W sezonie 1997/98 nowy klub zajął 2. miejsce w tabeli za Orlętami Łuków, minimalnie przegrywając walkę o prawo gry w barażach o II ligę. Od 1999 występował w IV lidze, a trzy lata później spadł do klasy okręgowej. W sezonie 2002/2003 wrócił na czwarty poziom rozgrywkowy.
mały|Podlasie Biała Podlaska-Stal Mielec 2009r. mały|Podlasie Biała Podlaska-Stal Mielec 2009r. mały|Podlasie Biała Podlaska-Stal Mielec 2009r. Podlasie Biała PodlaskaJest spadkobiercą historii i sukcesów MZKS-u. Do sezonu 2003/2004 klub przystępuje pod nową nazwą – MKS Podlasie. Jego głównym sponsorem został Urząd Miasta w Białej Podlaskiej. Po reorganizacji rozgrywek w sezonie 2008/2009 klub występował w nowej IV lidze. Podlasie zwyciężyło w niej bez porażki. W latach 2009–2015 zespół występował w lubelsko-podkarpackiej grupie III ligi, a w sezonie 2013/2014 zwyciężył Puchar Polski w województwie lubelskim. W rundzie przedwstępnej pucharu na szczeblu centralnym w sezonie 2014/2015 klub przegrał po rzutach karnych spotkanie z Górnikiem Wałbrzych. W tym samym sezonie spadł do IV ligi, jednak w następnym powrócił na czwarty szczebel rozgrywkowy, na którym obecnie występuje.