Mais si le chef de l'expédition était nommé, les officiers et les matelots qui devaient le suivre n'étaient pas choisis, et quant aux vaisseaux, il fallait renoncer à les trouver dans l'empire russe. On n'en rencontra pas davantage à Hambourg. Ce fut seulement à Londres que le capitaine Lisianskoï, futur second de Krusenstern, et le constructeur Kasoumoff, réussirent à se procurer deux bâtiments, qui leur parurent à peu près propres au but qu'on se proposait. Ils reçurent les noms de Nadiejeda et de Neva.
Sur ces entrefaites, le gouvernement résolut de profiter de cette expédition pour envoyer au Japon un ambassadeur, M. de Besanoff, avec une nombreuse suite et de magnifiques présents destinés au souverain du pays.
Le 4 août 1803, les deux bâtiments, complètement arrimés et portant cent trente-quatre personnes, quittèrent la rade de Cronstadt. Ils firent à Copenhague et à Falmouth des stations rapides, afin de remplacer une partie des salaisons achetées à Hambourg et de calfater la Nadiejeda, dont les coutures s'étaient ouvertes pendant un gros temps qui assaillit l'expédition dans la mer du Nord.
Après une courte relâche aux Canaries, Krusenstern chercha vainement, comme l'avait fait La Pérouse, l'île Ascençao, sur l'existence de laquelle les opinions étaient partagées depuis trois cents ans. Puis, il rallia le cap Frio, dont il ne put fixer exactement la position, malgré le vif désir qu'il en avait, car les relations et les cartes les plus récentes variaient entre 23° 06´ et 22° 34´. Après avoir eu connaissance de la côte du Brésil, il donna entre les îles de Gal et d'Alvarado, passage à tort signalé comme dangereux par La Pérouse, et entra, le 21 décembre 1803, à Sainte-Catherine.
La nécessité de remplacer le grand mât et le mât de misaine de la Neva arrêta, pendant cinq semaines, Krusenstern dans cette île, où il reçut des autorités portugaises l'accueil le plus empressé.
Le 4 février, les deux bâtiments purent reprendre leur voyage. Ils étaient préparés à affronter les dangers de la mer du Sud et à doubler le cap Horn, cet effroi des navigateurs.
Si le temps fut constamment beau jusqu'à la hauteur de la Terre des États, par contre, à des coups de vent d'une violence extrême, à des rafales de grêle et de neige, succédèrent des brouillards épais avec des lames extrêmement hautes et une grosse houle qui fatiguait les bâtiments. Le 24 mars, pendant une brume opaque, un peu au-dessus de l'embouchure occidentale du détroit de Magellan, les deux navires se perdirent de vue. Ils ne devaient plus se retrouver qu'à Nouka-Hiva.
Krusenstern, après avoir renoncé à toucher à l'île de Pâques, gagna l'archipel des Marquises ou Mendocines, et détermina la position des îles Fatougou et Ouahouga, nommées Washington par Ingraham, capitaine américain, et découvertes en 1791, peu de semaines avant le capitaine Marchand, qui les appela îles de la Révolution. Il vit Hiva-Hoa, la Dominica de Mendana, et rencontra à Nouka-Hiva un Anglais du nom de Roberts et un Français appelé Cabri, qui, par leur connaissance de la langue, lui rendirent d'importants services.
Les événements que relatent cette relâche n'offrent pas grand intérêt. Le récit de ceux que relatent les voyages de Cook peut s'appliquer à celui de Krusenstern. Mêmes détails sur l'incontinence aussi absolue qu'inconsciente des femmes, sur l'étendue des connaissances agricoles des naturels, sur leur avidité pour les instruments de fer.