Prvi međunarodni trofej stigao je u sezoni 1980/81. Nakon ekspresnog povratka u najviši rang u Odbojkaškom klubu Vojvodina odlučili su da se ozbiljno posvete budućnosti. Novosađani nisu više želeli da budu samo prolaznici u Prvoj saveznoj ligi, koji će da se bore za sredinu tabele i povremeno naprave koje iznenađenje, ili pak možda prigrle i neki pehar. Odlučna namera crveno-belima bila je da neke uspehe pretoče u konstatno dobre rezultate, koji će ih vinuti u sam vrh jugoslovenske odbojke.
Čak dvadeset imena našlo se na spisku, što je samo govorilo da će borba za mesto u timu biti žestoka. Vratili su se Stevan Vujasinović (iz Italije) i Dragan Nišić (iz Bosne), a u konkurenciji su bili novopridošli juniori Olajić, Miljanić i Savić. Odigrala je Vojvodina jake prijateljske utakmice, osvojila turnir posvećen Danu oslobođenja Novog Sada, na kojem je savladala ekipu Partizana i jakog Panatinaikosa iz Grčke.
Sezona je odlično počela, nakon osam kola samo jedan poraz zabeležen je od favorita šampionata, tima Mladosti. Sve je upućivalo na to da će Novosađani u toj sezoni biti jedini ozbiljni pratioci Zagrepčana, koji mogu ugroziti njihovo prvo mesto. Čvrsto su držali crveno-beli drugu poziciju, zatim nepotrebno izgubili od Ribnice, a onda u nastavku prvenstva u jednoj čudnoj utakmici, i u nenormalnim uslovima, i od poslednje ekipe na tabeli – Stavbara. Koliko su ti porazi bili presudni pokazalo se i nakon što je Mladost doživela prvi poraz.
Praktično su novosadski prvotimci pomogli Zagrepčanima da učvrste prvu poziciju, a šampionsku titulu Mladost je gotovo osigurala u međusobnom duelu s Vojvodinom, pobedivši 3:1. Kada je bilo jasno da ne mogu biti prvi, ali ni ispod drugog mesta puleni trenera Višekrune su malo i popustili, te su do kraja sezone stigla još tri poraza. Međutim, titula viceprvaka države bila je, ipak, veliki uspeh i podstrek za budućnost. Koliko je ovaj rezultat doneo elana potvrdilo je i to što je Vojvodina u svim selekcijama bila u punom pogonu i tokom juna.
U Kupu Vojvodina nije prikazala dovoljno kvalitetne igre kao u ligi. U prvom kolu lako je prošla Jedinstvo, ali ju je u osmini finala i to u Novom Sadu zaustavio raspoloženi Vardar.
Za nove izazove u sezoni 1981/82. ekipa Vojvodine se pripremala puna tri meseca, ozbiljno, marljivo, ambiciozno – kako na organizacionom, tako i na takmičarskom planu. Upravo zbog toga, teško je izdvojiti koji je od segmenata obeležio sezonu 1981/82. Jer, svaki je za sebe bio jednako važan. Takmičarski, bilo je uspešno na sva tri fronta: treće mesto u Prvenstvu Jugoslavije, drugo na finalnom turniru Kupa Jugoslavije i – još jedno drugo mesto, u Balkanskom kupu, što je do tada bio najveći uspeh na međunarodnoj sceni.
U odnosu na prethodnu sezonu sastav je bio neznatno izmenjen, a Vojvodina je uvek vodila računa da pogon bude dovoljno veliki, u slučaju zamora, bolesti, povreda…. Uoči početka Šampionata Jugoslavije Novosađani su najavili ne samo borbu za vrh tabele, nego i za nešto što im je nedostajalo kako bi slika sada već ozbiljnog i velikog kolektiva bila kompletna. Naime, još uvek crveno-beli nisu imali podršku publike koja bi odgovarala njihovim sportskim rezultatima. Jednim delom tome su kumovale i česte selidbe, neadekvatne, ili daleke sale. No, tada se „desio“ ulazak u Malu salu novog GSC „Vojvodina“ i to je bilo presudno ne samo za tu sezonu, nego i za budući trenažni i takmičarski program novosadskog kluba. Zato su se i u Upravi potrudili da marketinški odu korak dalje, te da u „Spens“ privuku publiku, osim dobrim partijama, i pomoću panoa, plakata, besplatnih ulaznica… Uskoro je Vojvodina dobila i prostorije u Lasla Gala 12, tako da je sve moglo da funkcioniše na mnogo višem nivou.
Predviđanja stručnjaka da će gornji dom formirati Mladost, Partizan, Vojvodina, Vardar i Bosna, pokazala su se tačnim, jer su upravo ovi timovi tokom čitave sezone odlučivali o plasmanu u samom vrhu. Posle četiri kola bez poraza su se izdvojili Mladost, Partizan i Vojvodina. Negde polovinom drugog dela sezone Zagrepčani su gotovo obezbedili odbranu titule, dok su se crno-beli i Novosađani borili za drugo i treće mesto. Dobre partije, možda koji neočekivani poraz, sve ukupno dobar utisak i na kraju – treće mesto za Vojvodinu. Slično je bilo i u Kupu Jugoslavije, do završnice su crveno-beli lako stigli, a onda u Beogradu izgubili samo od Mladosti i zauzeli drugo mesto na finalnom turniru. Dragan Nišić proglašen je za najboljeg smečera.
Najveći uspeh, bez sumnje, ostvaren je u Balkanskom kupu, gde je Vojvodina bila nadmoćna u duelu sa turskom Karsijakom, te u finalu naletela ne samo na rumunski Eksplorari, nego i na vrlo diskutabilne odluke sudija u revanš meču. Novosađani su Rumune savladali u prvom meču u „Spensu“ 3:1 i dobili veliki elan posle toga. No, kako su krenuli na revanš meč u Rumuniju, krenuli su i maleri. Najpre je vozač autobusa zalutao, pa je put do mesta Baja Mare trajao 16 časova, a sutradan pred polazak na utakmicu autobus nije mogao da upali, te su odbojkaši Vojvodine sa kompletnom opremom peške po poledici nekako stigli do sportske dvorane „Dačija“.
Uz sve to usledila je i nesebična pomoć domaćinu od strane grčko-turskog sudijskog para, najpre u prvom, a zatim i u trećem setu, koji je praktično već bio u rukama Vojvodine. Razmišljali su Novosađani i da napuste teren, posebno posle crvenog kartona i isključenja Dragana Nišića, ali su ipak odlučili da sportski završe ovaj susret. Ni izvinjenje domaćina, ni opaska trenera Eksplorarija da im „ni rumunske sudije ne bi tako pomogle“ nisu ublažili žal crveno-belih prvotimaca za prvim mestom. Iako je i drugo bilo izvanrendan uspeh.