W 1595 roku ruszyła kolejna wyprawa – dowodził nią Nay, a Barents był głównym pilotem. Wystawiono siedem statków, na pokładzie których podróżowali także kupcy z towarem. W ekspedycji uczestniczył ponownie Jan Huygen van Linschoten. Wypłynięto jednak zbyt późno i po dotarciu do Jugorskiego Szaru, okazało się, że cieśninę zaczynał już blokować lód. Pod naciskiem Barentsa wyprawa była kontynuowana – pokonano cieśninę i statki wpłynęły na Morze Karskie, lądując na wyspie z rzekomymi diamentami, które okazały się być potłuczonym szkłem. Barents namawiał Naya, by zimować w Arktyce i kontynuować podróż w kolejnym roku. Wśród załogi doszło do buntu, pięciu prowodyrów zostało powieszonych, a po nieudanej próbie dalszej podróży Nay podjął decyzję o powrocie do Holandii.
Wyprawa Naya przyniosła potężne straty fundatorom i zainteresowanie kierunkiem północno-wschodnim zmalało. Jednak wizja państwowej nagrody ustanowionej za odkrycie Przejścia Północno-Wschodniego, zachęciła kupców amsterdamskich do sfinansowania jeszcze jednej ekspedycji. Wysłano dwa statki pod dowództwem Jacoba van Heemskercka (1567–1607) i Jana Rijpa (1570-1613), a pilotem ponownie został Barents. Wyprawa miała podążać trasą Planciusa, który wierzył w istnienie otwartego morza polarnego bez lodu bliżej bieguna północnego.