W 1951 roku nastąpiła kolejna reorganizacja rozgrywek, dzięki której Stal trafiła do trzeciej grupy II ligi. W debiucie drużyna przegrała na wyjeździe z Górnikiem Wałbrzych 0:8, lecz mimo nieudanego początku zajęła czwarte miejsce, a rok później uplasowała się na szóstej pozycji.
Kolejne reorganizacje rozgrywek spowodowały, że klub trafił do nowo utworzonej III ligi, w której rywalizował (już jako Star) z innymi zespołami w latach 1955–1957. W 1958 roku powołano ligę okręgową, która stała się najwyższą klasą rozgrywkową w województwie kieleckim. W pierwszym sezonie starachowiczanie zajęli trzecie miejsce, przegrywając z Bronią Radom i Granatem Skarżysko-Kamienna. Dwa lata później Star zajął już pierwsze miejsce, ale nie wywalczył awansu w barażach ze Slavią Ruda Śląska. W 1965 roku po meczach barażowych starachowicka drużyna miała tyle samo punktów co Lech Poznań. Wymusiło to rozegranie dodatkowego meczu, który odbył się 5 sierpnia na stadionie Warszawianki i zakończył się wygraną rywali po golach zdobytych w dogrywce (w regulaminowym czasie gry było 1:1). Równie blisko wywalczenia awansu Star był rok później, gdy do upragnionego celu zabrakło jednej bramki. W sezonie 1965/1966 Star osiągnął także swój największy sukces w Pucharze Polski, docierając do 1/4 finału, gdzie uległ Pogoni Szczecin.