L'ipotesi dell'esistenza di questo passaggio per raggiungere le Indie orientali fu dapprima avanzata dagli inglesi, che tra il 1553 e il 1560 effettuarono le prime spedizioni (Hugh Willoughby, Richard Chancellor, Anthony Jenkinson), proseguite tra il 1594 e il 1607 da numerose spedizioni olandesi, tra cui una comandata da Willem Barents, che morì bloccato dai ghiacci dopo aver scoperto le coste meridionali delle Svalbard, o Spitzbergen (1597).

L'inglese Henry Hudson in tre successivi viaggi per conto della Compagnia della Moscovia, dell'Olanda e di una compagnia londinese integrò le scoperte di Barents ed entrò nello stretto tra Labrador e Terra di Baffin. Ulteriori tentativi furono compiuti sotto il patrocinio di Pietro il Grande a partire dal 1725 per opera del danese Vitus Bering che nel 1741 riuscì a scoprire il passaggio. Esso fu tuttavia attraversato per la prima volta soltanto nel 1879 dallo scienziato svedese Erik Nils Nordenskiöld.