Etter Willem Barentzs' forsøk i 1590-årene, var det lenge ingen forsøk på å trenge gjennom Nordostpassasjen. I årene 1734-43 drev Den store nordiske ekspedisjon vidstrakte undersøkelser langs Sibirkysten. En ledende skikkelse var dansken Vitus Bering. Han hadde alt i 1728 seilt gjennom Beringstredet.
En østeriksk-ungarsk polarekspedisjon 1872-74 under ledelse av Julius von Payer hadde også Nordostpassasjen som mål. De ble skrudd fast i isen ved nordspissen av Novaja Semlja og ett år senere skrudd opp mot sørkysten av Frans Josefs Land, som da ble oppdaget og utforsket. Her måtte fartøyet forlates, men ekspedisjonen klarte å redde seg tilbake til Novaja Semlja, før russiske fangsfartøyer førte dem til Vardø.
Adolf Erik Nordenskiöld (1832-1901) hadde forberedt seg godt ved flere rekognoseringsturer da han i 1878 reiste ut med Vega for å trenge gjennom Nordostpassasjen. Den første sommeren nådde han nesten fram -
ikke mange milene sto igjen da Vega frøs inne på nordsiden av Tsjuktsjerhalvøya. Sommeren 1879 var den første ferden gjennom Nordostpassasjen fullført.
Roald Amundsen seilte gjennom Nordostpassasjen med skuta Maud 1918-20. Maud måtte overvintre to ganger før den endelig kom igjennom.
