U sezoni 1958./59. „Radnik“ je igrao u Zeničkom podsavezu sa klubovima „Lašva“ Dolac, „Orlovik“ Žepče, „Radnički“ Bugojno, „Omladinac“ Guča Gora, „ZSK“ Zenica, „Borac“ Tetovo, „Borac“ Travnik, „Sloga“ Gornji Vakuf, „Elektrobosna“ Jajce, „Metalac“ Novi Travnik, „Jedinstvo“ Busovača, „Radnik“ Donji Vakuf i „Iskra“ Bugojno.
U sezoni 1959./60. došlo je do reorganizacije natjecanja pa su formirane zonske lige i to Zenička i Sarajevska. Niži rang bio je podsavezni. U Zeničkoj zoni natjecalo se deset ekipa: „Elektrobosna“ Jajce, „Krivaja“ Zavidovići, „Radnik“ Donji Vakuf, „ZSK“ Zenica, „Sloga“ Gornji Vakuf, „Vlašić“ Turbe, „Iskra“ Bugojno, „Bratstvo“ Novi Travnik, „Rudar“ Kakanj, „Radnički“ Zenica (kasnije „Čelik“). Vitežanima po rezultatima iz netom završene sezone u Zeničkoj zoni nije bilo mjesta i u sezoni 1959./60. natječu se u Podsaveznoj A grupi s klubovima: „Radnički“ Bugojno, „Metalac“ Novi Travnik, „Borac“ Travnik, „Sloboda“ Mrkonjić Grad, „Orlovik“ Žepče, „Tisovac“ Busovača, „Mladost“ Kakanj, „Radnički II“ Zenica, „Jedinstvo“ Busovača, „Borac“ Tetovo.
U sezoni 1961./62. „Radnik“ se natječe u Zonskoj ligi Zeničkog podsaveza, s klubovima:“Metalac“ Novi Travnik, „Vlašić“ Turbe, „ZSK“ Zenica, „Krivaja“ Zavodovići, „Elektrobosna“ Jajce, „Radnik“ Donji Vakuf, „Orlovik“ Žepče, „Željezničar“ Zenica i „Lašva“ Dolac. U ovoj sezoni „Radnik“ je pretrpio dva teška poraza od tada snažnog „ZSK“ iz Zenice. U prvom jesenskom kolu u Vitezu „ZSK“ je slavio s visokih 1:6, a u prvom proljetnom u Zenici bilo je čak 10:0. To je, koliko znamo, najveći poraz Vitežana u prvenstvenom utakmicama u dosadašnjoj povijesti kluba.
Naredne dvije sezone 1962./63. i 1963./64. „Radnik“ se s promjenjljivim uspjehom natjecao u Zeničkoj zonskoj ligi. Potom je došlo do reorganizacije natjecanja, pa su klubovi dotadašnje Zeničke zonske lige iz Bugojna, Donjeg i Gornjeg Vakufa, Jajca i
Mrkonjić Grada priključeni Međuopćinskoj ligi Banjalučkog nogometnog podsaveza.
Prema jednom od zapisnika Natjecateljske komisije Zeničke zonske lige iz sezone 1967./68., koji govori o plasmanu ekipe, ali se ne vidi je li to na kraju prvenstvene sezone ili nekoliko kola prije kraja, vodi „Krivaja“ Zavidovići s 28 bodova, a slijede:„Metalac“ Novi Travnik 24, „Radnik“ Vitez 22, „Borac“ Tetovo 19, „Borac“ Travnik 18, „Jedinstvo“ Busovača 16, „Sloga“ Gornji Vakuf 16 (-2), „Bistričak“ 15, „Željezničar“ Zenica 10 i „Lašva“ Dolac s 10 osvojenih bodova.
