Na początku XXI wieku zespół w walce o wysokie lokaty najczęściej ustępował lokalnemu rywalowi – Okocimskiemu Brzesko. W sezonie 2002/2003 BKS wyprzedził w tabeli Poprad Muszyna jednym punktem i zajął pierwsze miejsce w lidze, premiowane barażami o III ligę.
W dwumeczu barażowym o awans klub z Bochni zmierzył się z rezerwami Wisły Kraków. Faworytem był zespół Białej Gwiazdy, w składzie której widnieli tacy piłkarze, jak Paweł Brożek, Piotr Brożek, Daniel Dubicki czy Grzegorz Kmiecik. Na stadionie Wawelu padł rezultat 1:0 dla gospodarzy, a w Bochni mecz zakończył się remisem 1:1.
Baraże o III ligę, grupa IV
Najbliżej powtórzenia tego osiągnięcia klub był w sezonie 2004/2005. Na dwie kolejki przed końcem Bocheński KS liderował tabeli z dwupunktową przewagą nad Kolejarzem Stróże. Porażka w Woli Rzędzińskiej z tamtejszą Wolanią pozwoliła Kolejarzowi przejąć fotel lidera, a po zwycięskich barażach z Garbarnią Kraków awansować szczebel wyżej.