Jotenkin samallaisen matkan hän teki Norjasta vielä seuraavanakin vuonna, joka oli ankara jäävuosi. Näin oli hän jo kylliksi valmistuksia tehnyt viimeiselle, päättävälle matkalleen.
Koillisväylä.
Edellisillä jäämerimatkoilla oli Nordenksiöld'issä herännyt halu paremmin varustetulla matkueella jatkaa Jäämeren tutkimuksia etemmäksi itään ja jos mahdollista niin aina Beringin salmelle saakka. Tämä matkasuunnelma kun sitte oli valmistettu ja kypsynyt, esitteli Nordenskiöld sen Tammikuun 26 p. 1877, Ruotsin kuninkaalle Tukholman linnassa, jossa silloin oli läsnä paitsi kuninkaallinen perhe, meriministeri, rikas tieteiden suojelia, Göteborgin kauppamies Oskar Dickson ja likisimmät edellisillä jäämeriretkillä seuraajansa. Ihastuksella ja innolla hän esitteli sen suuren tarkoituksensa, että höyryn ja sähkön aikakausi voi tunkeuda tutkimuksille vielä vieraille aloille ja maailman keskusliikkeelle avata yli 90 leveysasteen avaran meren (Jenisein suusta Isoon Valtamereen), "jossa laivan savupatsasta ei vieläkään ole nähnyt." Tämän tarkoituksen täyttäminen on yhtä tärkeä, kuin mainion Cook'in Ison Valtameren tutkimusretket. Laveimmissakin piireissä löysi Nordenskiöldin toivo osan ottoa ja pian parkkilaiva Vega, apuhöyrykoneella varustettuna ja muuten mitä huolellisimmasti laitettuna, oli Göteborgin satamassa Nordenskiöldiä varten. Nordenskiöld väitti oikeudella, että ainoastaan oikean lähtö-ajan valitseminen ratkaisi matkan onnistumisen. Elokuussa täytyisi olla Aasian pohjaisrannikolla, koska silloin kulkujäät olisivat vähimmän haittana.
Eräs Venäläinen matkue oli jo v. 1740 Jenisein suusta saapunut 75:teen pohjaiseen leveysasteesen, mutta Aasian pohjaisin niemeke luultiin olevan 2 astetta ylempänä, sillä sinne, kerrottiin, oli eräs toinen Venäläinen, Prontschischew päässyt, vaikka tämä luulo oli kaukana varmuudesta.
Siinä tapauksessa ett'ei Nordenskiöldin pyrintö Koillisväylitse onnistuisi, oli kuitenkin hänen kokemuksensa ja tieteellisyytensä takauksena, että Aasian napasuhteet hänen kauttansa paljo selveneisivät.
Vegamatkueesen kuului professori Nordenskiöldin kanssa kuusi nuorta ja voimallista, hyvin valmistettua luonnontutkijata. Vegan päällikkö oli luutnantti Palander, rohkeudestaan ja taidostaan tunnettu merimies, joka jo ennen oli ottanut kahteen napamatkueesen osaa. Päällikön likisimpänä miehenä virkaa toimitti luutnantti Brusewitz, ja miehistöön kuului 17 merimiestä, laivastosta valituita, yksi Gotlantilainen merimies sekä kolme Tromsöstä otettua Norjalaista kalastajaa.
Heinäkuun 4 p:nä 1878 lähti Nordenskiöld Vegallaan merelle, koko Ruotsin kansan innollisimmalla osanotolla evästettynä. 14 päivää ennen oli jo kuormalaivat Fraser, kapteeni Nilsson'in johdolla, ja Lena, kapteeni Johannesen'in johdolla, ja sittemmin vielä Lontoosta ruotsalainen purjelaiva Ekspress, kapteeni Grundersen'in johdolla lähteneet Jenisein suulle. Kaksi höyrylaivaa näistä vei Vegalle varatavaroita, jos, nimittäin, se jäisi johonkin talveksi ja purjelaivalla taas oli hiiltä näille kolmelle höyrylaivalle. Kaikkien näiden laivojen piti yritystä edistää.
Se mielten jännitys, jolla koko Euroopa matkueen kulkua seurasi, tuli jo Lokakuun 14 p:nä jollakin tavalla rauhoitetuksi — lohdullisemmasti kuin kukaan odottikaan, sillä Vega lähetti sähkösanoman Jakutskista, Lenan oikealta rannalta. Sittekuin "Fraser" ja "Ekspresse" jo Jenisein suussa olivat Vegasta eronneet, mennäkseen tätä virtaa ylöspäin, oli "Lena" Lena-virran suussa myös siitä eronnut, mennäkseen sekin virtaa ylös Jakutskiin (63° pohjaista leveyttä). Täältä lähetettiin nyt ensin sähkösanoma ja sitte vielä kirje Euroopaan. Nordenskiöldin ja Palanderin itsensä lähettämä sähkösanoma vahvisti edelliset ilmoitukset, että laiva oli onnellisesti päässyt Aasian pohjaisimman niemen, Kap Tscheljuskin ympäri ja tullut Lenan suuhun. Loppumatka Aasian itäisellä rannikolla ei voinut enää tarjota vaikeampia vastuksia. Näin siis tuo kauvan etsitty tie oli jo löytymäisillään. Tällä ajalla saapunut, Jenisein rannalla olevasta Dicksonin satamasta Nordenskiöldin kirjoittama kirje kertoi sitte tarkemmin heidän matkansa siihen asti.
Kap Tscheljuskin niemen ympäri purjehtiminen oli silloisen myrskyn ja vastatuulen tähden hyvin vaikea. Laiva ei kuitenkaan kohdannut jäitä, vaikka se meni niin pohjaisitse kuin mahdollista. Kemi kun oli kierretty, pysyttiin likempänä rantaa, joten voitiin näihin asti tehdyt kartat huomata epävarmoiksi, ja niiden määräämän pohjaisuuden rajan nähtiin joskus olevan 11 astetta todellisuutta etelämpänä. Ilmastolliset suhteet olivat v. 1878 erittäin myöteisiä tämmöiselle matkalle, ja Palander'in tarkemman rannikkokartan toimittaminen kävi siis erinomaisen hyvin. Aasian pohjaisin paikka, 1,000 jalkaa meren pinnan ylitse kohoutuva kallioniemeke, on näiden määräysten mukaan 77° 43', pohjaista leveyttä, ja 104° 1', itäistä pituutta, kohdalla. Vega sivuutti sen Elokuun 20 p:nä 1878. 7 päivänä sen jälkeen voitiin laiva ankkuroida Lenan suuhun, joka nyt tehtyin laskuin mukaan näytti olevan ennen merkitty liika kauvaksi itään.
Tähän asti ilmoitukset olivat menneet Euroopaan jotenkin hyvin, mutta tästä alkain ei tiedetty matkueen kohtalosta mitään. Sentähden asia alkoi jo todellisesti huolettaa, varsinkin sitte, kun Amerikalaiset valaiden pyytäjät kertoivat, että he Lenan itäpuolella olivat nähneet ison höyrylaivan jäässä kiinni. Asiaa harrastavainen Venäläinen, laivan varustaja Sibiriakoff päätti siis Toukokuussa 1879 Beringin salmen kautta lähettää höyrylaivan "Nordenskiöld" Vegaa etsimään.