Крај осме и прва половина девете деценије прошлог века нису донели пуно радости навијачима Војводине. Олуја која је фебруара 1979. године уништила кров изнад западне трибине градског стадиона као да је најављивала бурне године у историји најпопуларнијег војвођанског клуба. У сезони 1978/79 Новосађани су заузели дванаесто место на прволигашкој табели, да би се следеће сезоне нашли у још неповољнијем положају, грчевито се борећи да сачувају статус у елитном друштву. То им је успело само захваљујући томе што су успели да сакупе бод више од претпоследњег Осијека, који је имао чак и бољу гол разлику од Војводине. Само у сезони 1982/83 ФК „Војводина“ Нови Сад је успела да заврши у горњем делу табеле, на деветом месту. Наредну сезону такође нису обележили резултати, али јесте долазак првог странца у редове црвено-белих у послератној историји, када је уговор са Новосађанима потписао репрезентативац Габона, Анселм Делика, који је брзо добио домаћи надимак – Жика. Једини блесак црвено-бели су имали када су у сезони 1984/85 успели да се пласирају у полуфинале националног купа. Црвено-бели дрес су тада носили заиста талентовани фудбалери: Ћирић, Илић, Мићановић, Новаковић, Димитрић, Рац, Ђуровић, Вукадиновић, Тинтар, Зовко, Ћурчић, Марић, Беквалац, Грубор, Мокуш, Мијић, Врга; али Војводина је све више и више резултатски тонула. Ту исту сезону Воша је првенство завршила на шеснаестом месту, што је било увод у оно што ће уследити годину дана касније. У сезони 1985/86 године, у којој се на клупи Војводине променило чак пет тренера, дно је коначно додирнуто и Војводина је као убедљиво најслабије пласирани тим завршила такмичење и испала у нижи ранг такмичења, у Другу лигу, група запад.

Некад се мора пасти да би се могло устати и кренути напред. Ове речи би најбоље описале будућа догађања око Војводине. Снаге су консолидоване, поново је стављен акценат на играче из властитог погона и Војводина се под палицом тренера Тонка Вукушића експресно вратила у друштво најбољих клубова некадашње Југославије. Агилно руководство које су предводили технички директор клуба Љубо Шпањол, а затим за њим Милорад Косановић, успело је да у сезони 1987/88 окупи сјајан тим, који ће следеће године доказати своје велике могућности. Као појачања у тим Новосађана су стигли Марас, Јокановић, Воркапић, Тањга, Михајловић, Пунишић, Карталија и ветеран Милош Шестић, док су са позајмице враћени Дакић и Мијић. Шансу да предводи ову генерацију играча добио је тада млади стручњак Љупко Петровић. Тако је започела прича друге шампионске титуле која је стигла у Нови Сад у сезони 1988/89. Тим који је имао зацртан план да у првој сезони буде стабилан прволигаш, а да у наредним постане конкурентан тимовима „велике четворке“, неочекивано је направио узлет већ по формирању! Војводина је на опште изненађење готово цело првенство била на првом месту и на крају сасвим залужено стигла да трофеја. Овај тим, који је имао подршку навијача као ни један до тада, предводио је Милош Шестић. Популарном Шелету је, због његових година, али и изражених вештина у баратању са лоптом и фудбалске интелигенције, дата улога „слободног стрелца“, лишен је обавезних тактичких задатака и имао је потпуну слободу у игри. Испоставило се да је то била добитна комбинација, јер се Шеле баш у тој улози сналазио као риба у води, те се и дан-данас памте његови потези и голови, бравуре које је правио потпуно искоришћавајући „одрешене ноге“ дате од стране тренера. За офанзивне задатке по боковима били су задужени Михајловић и Јокановић, први неуморан тркач са убојитом левицом од које су страховали голмани, други дисциплиновани извршитељ тактичких поставки, са израженим осећајем за скок игру. Бедем испред гола чинили су штопери Миловац и Карталија, док су бековски део посла обављали Мијић и Вујачић. Средину терена покривали су Шапурић и Пунишић, док су друштво Шестићу у нападу правили Воркапић или Јоксимовић. Мрежу је чувао незамењиви Чеда Марас, једини који је одиграо све 34 утакмице у шампионату и чије су вештине у одбрани једанаестераца умногоме допринеле освајању круне. Наиме, тада је важило правило да се у случају нерешеног резултата након 90 минута изводе пенали, при чему је победник пенал-серије добијао један бод, а поражени остајао празних шака. На опште изненађење целокупне спортске јавности, млади тим Војводине од почетка је заузео врх првенствене табеле и није га испуштао до самог краја. Кључни тријумф остварен је у 26. колу, када је у Новом Саду савладан најозбиљнији конкурент за престо, Црвена Звезда, са 3:1. Након тога, био је утабан пут да се титула после 23 дуге године врати у Нови Сад. Она је и оверена у дуелу са Слободом из Тузле у претпоследњем колу, када је пред крцатим трибинама градског стадиона у Новом Саду Милош Шестић прошао целокупну одбрану гостију и голмана, и са лоптом се ушетао у празну мрежу, поставивши коначних 4:2 и означио почетак велике феште на стадиону и улицама Новог Сада. Воша је тако освојила другу титулу у својој историји, а поред горенаведених играча било би некоректно не поменути и остале који су дали свој допринос том величанственом успеху: Поповића, Мијуцића, Дакића, Гаћешу, Тањгу, Марковића, Милосављевића, …

Ово је био изузетно млад тим од кога су се велики резултати тек очекивали, али након „антибирикоратске револуције“ (доласка Милошевића на власт) Војводина губи подршку челних људи покрајине, града и привреде и ради преживљавања била је принуђена да распрода свој шампионски тим најљућим ривалима из Београда. Следеће сезоне Војводина је несрећно испала у првом колу Купа европских шампиона од будимпештанског Хонведа. Прву утакмицу на страни Војводина је изгубила са 1:0, док је у другом мечу у Новом Саду тријумфовала са 2:1 (аутогол је дао Гаћеша), али то је било премало за пролаз у друго коло.

Продајом својих најбољих играча, Новосађани су осудили себе на резултатску просечност, те у сезони 1989/90 нису успели чак ни да се нађу у горњем делу табеле. Утисак је мало поправљен освајањем седмог места у наредном првенству, које ће, испоставило се, бити последње у држави званој СФР Југославија. Започели су сукоби на територији Словеније и Хрватске, уместо лопте проговорило је оружје, и фудбал је склизнуо у други план…