Помощником Крузенштерна и командиром второго корабля был назначен по рекомендации самого Крузенштерна его друг Юрий Федорович Лисянский, которого Крузенштерн характеризовал как:
«…человека беспристрастного, послушного, усердного к общей пользе… имевшего как о морях, по коим нам плыть надлежало, так и о морской астрономии в нынешнем усовершенствованном ее состоянии достаточные познания».
Несмотря на то, что в России уже сто лет строились добротные военные корабли, приобрести корабли для кругосветного плавания решено было за границей, в Англии, где уже был опыт строительства кораблей для длительных путешествий. В Англию выехали Лисянский и Розумов. С большим трудом им удалось купить два подходящих шлюпа водоизмещением один 450, другой 370 тонн. Обошлись они очень дорого, так как кроме 17 тысяч фунтов стерлингов, которые взяли за них судовладельцы, пришлось заплатить еще 5 тысяч фунтов стерлингов за ремонт.
В июне 1803 года Лисянский привел шлюпы в Россию. Больший из них был назван «Надеждой», а меньший — «Невой».
Не обошлось без трений между руководителями экспедиции и морским ведомством и по вопросу о комплектовании команд.
«Мне советовали, — писал Крузенштерн, — принять несколько и иностранных матросов, но я, зная преимущественные свойства российских, коих даже и английским предпочитаю, совету сему последовать не согласился».
В те времена в армию и флот брали крепостных, и обычно никто не считался с желанием этих людей. Но Крузенштерн и Лисянский считали, что такой метод комплектования экипажей кораблей, уходящих в длительное плавание, неприемлем, и добились разрешения набирать команды из желающих.
Охотников идти в кругосветное плавание оказалось очень много:
«…Если бы принять всех охотников, явившихся с просьбами о назначении их в сие путешествие, — писал Крузенштерн, — то мог бы я укомплектовать многие и большие корабли отборными матросами Российского флота».
Тщательно подбирался и офицерский состав. В поход с Крузенштерном и Лисянским пошли действительно лучшие офицеры русского военного флота. Среди офицеров «Надежды» были такие опытные моряки, как старший лейтенант М. И. Ратманов — участник многих боевых кампаний на Балтийском, Черном и Адриатическом морях, лейтенант Петр Головачев, мичман Фаддей Беллинсгаузен, открывший впоследствии вместе с М. П. Лазаревым Антарктиду; на «Неве» служили лейтенанты Павел Арбузов и Петр Повалишин, мичман Федор Коведяев и Василий Верх, впоследствии видный историк флота, и другие.
Именами этих людей русские мореплаватели впоследствии назвали острова, проливы, моря, бухты и другие открытые ими географические пункты.
27 июля 1803 года шлюпы вышли в море. После десятидневного плавания «Надежда» и «Нева» прибыли в Копенгаген.
С момента выхода кораблей в плавание Крузенштерн и Лисянский регулярно вели метеорологические и гидрологические наблюдения. Вскоре они заметили, что с продвижением на юг свечение воды увеличивается.
Плавание к берегам Бразилии, длившееся почти два месяца, оказалось очень изнурительным. Корабли шли в тропических и экваториальных широтах. Слабые переменные ветры сменялись шквалами, бури — штилями, жаркие и душные дни — не приносившими прохлады ночами.
14 ноября 1803 года русские корабли впервые в истории русского флота пересекли экватор. Забравшись на ванты, матросы обоих кораблей троекратным раскатистым «ура» поздравили друг друга с этим знаменательным событием в истории отечественного мореплавания.
У бразильского острова Святой Екатерины шлюпы были встречены туземцами, которые предложили провести «Надежду» и «Неву» проливом между островами Альварадо и Гал к месту стоянки. Согласно описанию Лаперуза, этот пролив считался весьма опасным для плавания, поэтому Крузенштерн и Лисянский охотно воспользовались услугами местных жителей. Каково же было их удивление, когда эти сведения не подтвердились.
Как и вся Бразилия, остров Святой Екатерины принадлежал в то время Португалии, которая широко использовала труд невольников-рабов. На острове процветала работорговля. Сюда из Анголы, Бенгуэлы и Мозамбика (Африка) приходили транспорты с неграми.