Yllämainittujen valmisteleväin matkainsa jälkeen Nordenskiöld saattoi ryhtyä täydellä todella suunnittelemaan tuon vuosisataisen suurtehtävän ratkaisemista, jonka vuoksi uuden ajan alusta saakka oli niin paljon uhrauksia tehty: laivamatkaa Aasian pohjoispuolitse Tyynelle merelle. Kenellä toisella olisikaan ollut siihen yhtä hyvät edellytykset! Amerikkalainen napamatkustaja Greely lausuu hänestä:
»Tämän nukkuvan kysymyksen saattoi jälleen päiväjärjestykseen ponnistuksillaan mies, jonka harrastukset ja toimet arktisissa asioissa olivat semmoiset, että ne kysymyksen ratkaisemiseen takasivat tieteellisen ja tarmokkaan pyrkimyksen; tämä mies oli Adolf Erik Nordenskiöld. Suomessa syntyneenä v. 1832 hän oli napamaissa toiminut laajemmalta kuin ainoakaan toinen tutkija ja hänen työnsä on ennen kuulumattomassa määrässä rikastuttanut ja hyödyttänyt ihmiskuntaa tärkeillä tuloksilla. Beringin merestä Grönlantiin, Huippuvuorilta Novaja Zemljahan ja Pohjois-Aasiaan saakka ovat hänen matkansa poikkeuksetta edistäneet tieteen asiaa, hyödyttäneet kauppaa ja olleet muille tutkijoille rohkaisuksi.»
Niin pitkän, menestyksellisen ja suuressa määrin onnenkin suosiman arktisen tutkijatoiminnan jälkeen Nordenskiöldin ei ollut vaikea saada varoja ja kannatusta yritykselle, josta oli tuleva hänen arktisen tutkijatoimensa suurin saavutus. Suurimman osan koillisväylän kulkemiseen tarvittavissa varoista, 300.000 markkaa, antoi jälleen gööteporilainen Oscar Dickson, kuningas Oskar antoi 11.000 mk ja kauppias Sibiriakow saman verran. Ruotsin valtiopäivät antoivat varoja »Vega» nimisen pyyntialuksen varustamiseen.
»Vega» ei tosin ollut erikoisesti rakennettu tätä retkeä varten, mutta samanlaisia vaikeuksia se kyllä oli suunniteltu kestämään, se kun oli puolta vuosikymmentä aikaisemmin rakennettu Jäämerelle valaanpyyntilaivaksi. Se oli kauttaaltaan tammea, jäänpuristusta varten vahvistettu, ulkopuolelta vahvalla kovapuisella jäänsuojuksella peitetty, tilavuudeltaan 357 tonnia. Sillä oli höyrykone, jonka voimalla se kulki noin 6—7 solmua tunnissa, sekä parkkitaklaus. Matkaa varten sitä tietysti oli koko joukon muutettava, varsinkin sisustusta, mutta kaiken kaikkiaan se oli tarkoitukseensa niin hyvä laiva kuin toivoa saattoi. Laivan päällikkönä oli Arnold Louis Palander, joka jo ennen oli purjehtinut Nordenskiöldin keralla (»Polhemin» kapteenina vv. 1872—73). Tiedemiehiä lähti mukaan F.R. Kjellman, kasvitieteilijä, A.J. Stuxberg, eläintieteilijä, ja E. Almqvist, lääkäri, jäkäläin tuntija, jota paitsi laivan upseerit niinikään hoitivat kukin tieteellistäkin työvelvollisuutta, italialainen G. Bove meritutkimuksia ja tanskalainen A. Hovgaard magneettisia ja ilmatieteellisiä havainnolta. Suomalainen O. Nordqvist seurasi mukana tulkkina ja apulais-zoloogina. Laivan miehistö oli Ruotsin laivastosta valittu, kauttaaltaan koeteltua, kunnollista väkeä. Kolme mursunpyytäjääkin oli mukana. Kolme laivaa seurasi mukana alkumatkalle noustakseen tavarakuormineen Siperian jokiin, höyrylaiva »Fraser» ja purjelaiva »Express» Jenisseihin ja uusi pieni »Lena» niminen höyrylaiva Lenaan.
»Vega» lähti Gööteporista heinäkuun 4:ntenä 1878, suunnaten ensin Tromsaan, josta Nordenskiöld itse tuli laivaan. Ankarat myrskyt pidättelivät siellä laivaa. Kara-merestä palaavat valaanpyytäjät pelottelivat retkikuntaa sillä tiedolla, että muka jääsuhteet siellä paraillaan olivat niin epäsuotuisat kuin suinkin. Matkalla Novaja Zemljahan ei kuitenkaan näkynyt jäitä ensinkään ja »Vega» kulki vastuksia kohtaamatta Waigatshin ja mantereen väliseen Jugor Sharriin, johon se pienen Habarowa nimisen pyydystäjäkylän eteen kävi ankkuriin; tämä nimittäin oli kaikille laivoille edeltä määrätty yhtymäpaikka.
Waigatshilla.
Täällä asui kesällä koko joukon samojedeja, joiden porolaumat kävivät laitumella Waigatshilla ja mannerrannikon tundroilla, sekä venäläisiä ja venäläistyneitä suomalaisia, kauppiaita, kalastajia ja pyyntimiehiä. Nordenskiöld oli jo kolme vuotta aikaisemmin käynyt Habarowassa, joten hän tuli vanhana tuttuna. Nyt hän käytti tilaisuutta hankkiakseen samojedeilta kansatieteellisiä esineitä, varsinkin epäjumalankuvia ja naisten vaatteita. Eräs venäläinen opasti hänet Waigatsh saarella olevalle samojedilaiselle uhrikummulle, vaikka venäläisetkin niitä taikauskoisen pelon vuoksi kammosivat. Tämä käynti ei kuitenkaan häirinnyt ystävällistä seurustelua samojedien kanssa, jotka tyytyivät siihen vakuutukseen, että kyllä jumalat kostavat puolestaan.
Kara-merellä, koillisväylän pahamaineisessa »jääkellarissa», ei nyt tavattu jäitä paljon ensinkään. Idempänä veden suolapitoisuus väheni siihen määrään, että se melkein kelpasi juotavaksi, mutta väriltään se oli keltaisenharmaata ja läpinäkymätöntä, niin että laivat kulkivat kuin savivellissä. »Olemme epäilemättä Ob-Jenissein virta-alueella». Meren syvyys oli monessa kohden vain kymmenkunta metriä, mutta kun pohja oli hyvin laakeata, ei karille ajosta ollut paljoakaan pelkoa. Elokuun 6:ntena »Vega» laski Jenissein suuhun Dixonin satamaan, jonka Nordenskiöld oli v. 1875 löytänyt ja jonka hän suojatun asemansa ja hyvän ankkuripohjansa vuoksi luuli tulevaisuudessa kehittyvän tärkeäksi kauppapaikaksi, vaikka siinä vielä v. 1878 samoili jääkarhuja ja peuroja.
Jenissein ajopuut.
Sama lienee kyllä laita vielä tänäpäivänäkin. Satamassa oli niin kosolta ajopuita, että merenkulkija sieltä helposti sai polttopuu-tarpeensa. Suurin osa Jenissein tuomista ajopuista kulkee kuitenkin mereen, jossa ne ajelevat edelleen merivirtain keralla, kunnes joko vettyneinä vajoavat pohjaan, tai kulkevat Novaja Zemljan, Siperian, Huippuvuorien ja Grönlanninkin rannoille saakka. Osa puista juuttuu Jenissein omaan uomaan, ennenkuin on vielä mereen ennättänytkään, tai muodostaa rannoille suuria ryteikköjä.