Naredne tri sezone, do kraja osamdesetih, obeležili su ispadanje iz Prve savezne lige, promene u strukturi kluba i ekspresni povratak u elitu.
Sezonu 1977/78. Vojvodina je počela takmičenjem u Kupu Jugoslavije. Aktuelni branilac pehara se nije proslavio, neočekivano je pao već na prvoj prepreci, izgubivši od ekipe VGSK rezultatom 2:3. Preselili su se crveno-beli u salu na Sajmištu, u kojoj je trener Dušan Višekruna pripremao gotovo nepromenjen tim, u odnosu na prethodnu sezonu, za bržu, borbeniju i moderniju igru. Iščekivala je Vojvodina ne samo domaći šampionat, nego i novi izazov, prvo učešće u jednom evropskom kupu (pravo na to ostvarila osvajanjem Kupa Jugoslavije prethodne sezone). Igranje u Kupu pobednika kupova donelo je i novu dimenziju klubu, značajno iskustvo i novu vrednost. Ipak, žreb je hteo da na startu Novosađani dobiju velikog rivala, italijansku ekipu Paoleti, od koje su u prvom kolu, u prvom meču izgubili u Kataniji 0:3. Prolaz u drugo kolo vodila je samo maksimalna pobeda u revanšu i to uz odgovarajuću poen razliku. U sali na Sajmištu lepo su počeli crveno-beli, poveli 2:0 (15:7, 15:3), nakon toga izgubili treći set, te je krajnja pobeda od 3:1 bila – pirova.
Prvo učešće u evropskom kupu donelo je i jednu novu poteškoću, sa kojom se do tada Novosađani nisu susretali. Zgusnut raspored (igranje i na domaćoj i na međunarodnoj sceni) doneo je mnogo više utakmica nego treninga i neminovan umor. Vojvodina se na početku dobro držala, imala je briljantan start u Prvoj saveznoj ligi, pet pobeda u prvih pet kola. U tom periodu pao je i aktuelni prvak, ekipa Mladosti. No, posle toga zamor je uzeo danak, te su usledila tri poraza. Uspeli su da dođu sebi puleni trenera Dušana Višekrune, igrali su u nastavku ponovo dobro, beležili i pobede i poraze, još jednom je pao šampion, a sezonu su završili na sasvim solidnom šestom mestu – najboljem do tada. Sve do neočekivanih poraza u martu od Rabotničkog i Jedinstva Vojvodina je bila u igri za prvo mesto, a snove je i definitivno raspršio Partizan pobedom na Sajmištu.
Prva nagrada
Krajem 1977. kada su se, već po tradiciji, sumirali utisci o protekloj godini, prvi put je nagrada na jednom izboru najboljih sportista otišla u ruke prvotimcu Vojvodine. Mihal Potran je proglašen za najboljeg odbojkaša u pokrajini, u okviru izbora lista „Dnevnik“.
Posle dve veoma dobre sezone usledio je bolni pad u sezoni 1978/79. i posle sedam godina gubljenje prvoligaškog statusa. Bilo je to nešto na šta Vojvodina nije računala – svi u taboru Novosađana bili su sigurni da imaju potencijal za dalji napredak. I na početku sezone sve je manje-više išlo ka tome.
Iako malo desetkovana zbog povreda, Vojvodina je beležila solidne rezultate. Bilo je očigledno da neće biti u vrhu, ali su se crveno-beli dosta dugo držali oko zlatne sredine. Činjenica je da je Novosađanima nedostajala čvrstina i istrajnost, jer je nekoliko, možda i presudnih, utakmica gubila u petom setu. Alarm je upaljen u 17. kolu, nakon kojeg su usledili šareni i nedovoljno dobri rezultati. Imperativ pobeda kao da je vezao i ruke i noge igračima Vojvodine, a strepnja je produžena posle poraza od Partizana na domaćem terenu. Posle toga, svako kolo bilo je odlučujuće, a u tome se Vojvodina definitivno nije snašla. Iako je u poslednjem kolu savladala Modriču, ipak je zauzela 11. mesto, jer je Rabotnički bio bolji od Rijeke.
Neočekivano ispadanje iz Prve savezne lige, problemi i loši odnosni inicirali su neminovne promene. U junu 1979. na vanrednoj konferenciji izabrana je nova Uprava i najavljena promena trenera. Za predsednika je izabran Rajko Kijac, Izvršni odbor činio je 21 član, dok su u sastavu Sekreterijara (najoperativnijeg tela kluba) bili podpredsednici Mirko Luburić i Nikola Pavlović, zatim generalni sekretar Branislav Otić i Slobodan Galešev. Novo rukovodstvo održalo je i sastanak sa igračima i najavilo borbu za drugačiji vid poslovanja i finansiranja, kako se ne bi stalno „prosjačilo“. Takođe je najavljeno i to da novi trener više neće imati profesionalni ugovor sa SOFK-om, već će direktno odgovarati Upravi kluba, pod čijim će nadzorom raditi i treneri mlađih kategorija.
U sezoni 1979/80. već posle nekoliko utakmica bilo je jasno da Vojvodini nije mesto među drugoligašima, te da je ispadanje iz elite bio sticaj raznih okolnosti i dobra škola u pravom času, koja je pomogla novosadskom klubu da i u budućnosti položi mnogo teže ispite.
Naime, igrački kadar u odnosu na prethodnu sezonu bio je skoro nepromenjen. Smena generacija nije bila velika, a mlađa garda, koja je priključena prvom timu, bila je pravi temelj za godine koje su sledile. I rad u klubu postao je ozbiljniji, kako u organizacionom delu, tako i u trenerskom. Novoizabrani prvi trener Srđan Ilić odlično je vodio tim, koji jednostavno nije imao ravnopravnog protivnika.
U osamnaest kola Vojvodina je ostvarila isto toliko pobeda, izgubila samo dva seta i tako osvojila prvo mesto u Drugoj saveznoj ligi Sever. Ubedljiva je bila i u kvalifikacijama u kojima je savladala pobednika južne grupe ekipu REMHK Kosovo 3:0. Lako su crveno-beli stigli i do pehara Kupa Vojvodine, pobedivši u finalu ekipu subotičkog Spartaka 3:0, te nastavili takmičenje u osmini finala Kupa Jugoslavije.
Dominacija nad rivalima dala je prostora i dojučerašnjim juniorima da pokažu talenat i uhvate zalet za buduće izazove. Rad sa mlađim kategorijama još jedan je segment kluba koji je procvetao. Omladinska ekipa uključila se u Kvalitetnu vojvođansku ligu i, poput seniorske, takođe ostvarila maksimalan učinak.
Osnovane su i dve pionirske škole pri osnovnim školama „Kosta Trifković“ u Novom Sadu i „Heroj Pinki“ u Futogu.