W sezonie 1971/72 ponownie zwyciężył klasę okręgową, by dzięki temu powrócić do III ligi.
Lata 1973–1988 Mimo iż początek klubowi dała piłka nożna, piłkarze przez długi czas nie potrafili się przebić do rozgrywek centralnych. Przełomowym momentem dla rozwoju futbolu w Olsztynie była budowa Olsztyńskich Zakładów Opon Samochodowych. Wówczas coraz więcej mówiło się o powstaniu w Olsztynie zespołu piłkarskiego, mającego walczyć o najwyższe trofea w Polsce. Osobą o największych zasługach w tychże staraniach był Władysław Leonhard, dyrektor OZOS. Jego starania wspierał m.in. Józef Buziński, ówczesny I sekretarz KW PZPR. Od strony sportowej podwaliny pod piłkarską drużynę kładli zawodnicy trenowani przez Andrzeja Cehelika, Leona Wolnego i Henryka Szczepańskiego. Brak funduszy sprawił, iż na początku lat 70. XX wieku stawiano przede wszystkim na zdolnych piłkarzy wywodzących się z regionu. Drużynę złożoną z miejscowych zawodników uzupełniono czterema piłkarzami Odry Opole, mającymi I-ligowe doświadczenie. Wiosną 1973 roku klub po raz pierwszy w historii zapewnił sobie awans do II ligi. Ówczesna przygoda z II ligą trwała dwa sezony. W pierwszym piłkarze zdołali zająć 12 miejsce, ostatnie zapewniające utrzymanie się w tejże klasie rozgrywkowej.