Лишь после назначения на пост главы Коммерц-коллегии графа Н.П. Румянцева, а в Адмиралтейств-коллегию Н.С. Мордвинова делу был дан ход.
Проектом Крузенштерна заинтересовалось также управление Российско-Американской компании, что позволило еще более ускорить подготовку к экспедиции. Все расходы по ее организации правление компании и, прежде всего ее руководитель Н.П. Резанов, решили взять на себя. Морское министерство во главе с Мордвиновым назначило начальником экспедиции Крузенштерна. Сам он избрал своим помощником Юрия Лисянского.
В задачу экспедиции входила доставка в поселения Русской Америки продовольствия и других товаров, обследование положения американских колоний, перевозка партии пушнины в Кантон и доставка в Японию русского посольства во главе с Резановым.
Руководство компании не было уверено в опытности морских офицеров и предложило Крузенштерну нанять для службы на кораблях иностранных моряков. Однако он наотрез отказался от подобного предложения и согласился принять на борт шлюпов «Надежда» и «Нева» лишь иностранных ученых.
7 августа 1803 года оба шлюпа снялись с Кронштадтского рейда и вышли в море.
Руководитель экспедиции вначале предполагал идти через Северное море к побережью Великобритании, оттуда двигаться в Атлантический океан к берегам Южной Америки. Обогнув мыс Горн, корабли вышли в Тихий океан и здесь у Сандвичевых островов разошлись. «Надежда» шла к берегам Японии, чтобы доставить российское посольство, что и являлось официальной целью экспедиции. Лишь после выполнения этой миссии «Надежда» шла к Кантону, где соединялась с «Невой» для совместного кругосветного плавания.
В октябре оба шлюпа уже находились в Атлантическом океане, а 26 ноября «Надежда» и «Нева» пересекли экватор.
На подходе к Южной Америке оба судна попали в жестокий шторм, сопровождавшийся грозой и шквалистым ветром. В наиболее опасный момент, когда начался ураган, он погнал оба судна навстречу друг другу. Искусство капитанов обоих шлюпов и умелые действия команды предотвратили столкновение. Однако шторм отнес «Надежду» и «Неву» далеко в море и только 20 декабря команда увидела на горизонте землю.
К вечеру следующего дня шлюпы подошли к острову Св. Екатерины, недалеко от крепости Санта-Круц. В связи с ремонтом «Невы» корабли задержались здесь почти на два месяца. Это дало Крузенштерну возможность ближе познакомиться с природой острова и его населением, собрать здесь образцы 90 видов растений, а также произвести астрономические наблюдения.
Однако Крузенштерн видел и темные стороны острова: «Всеобщая бедность народа, в высочайшей степени разврат женского пола и толпы тучных монахов, шатающихся ночью по улицам для услаждения чувств своих — суть такие отличия сего города… Инквизиция господствует здесь равномерно, как и во всех владениях испанских, и притом, по уверению многих, с великою строгостию… Для человека, свободно мыслящего, ужасно жить в таком месте, где злость инквизиции и неограниченное самовластие губернатора действует в полной силе, располагающей жизнью и смертью каждого гражданина… Здешний гражданин не имеет ни малейшей свободы».
Крузенштерн взял курс на юго-запад. Приближался мыс Горн — одно из самых главных препятствий для всех моряков. Многие мореплаватели, бывавшие здесь прежде, писали о бурях, часто разыгрывающихся в этих местах. Однако переход удалось совершить благополучно, и вскоре оба корабля вышли в Тихий океан.
Но 24 марта «Надежда» и «Нева», попав в полосу густого тумана, потеряли друг друга из виду и встретились лишь в бухте острова Нукачива — одного из группы Маркизских островов.
Простояв здесь около десяти дней, шлюпы направились к Гавайским островам, где, как ими было условлено заранее, встретились. 10 июля «Надежда» отправилась к берегам Камчатки, куда и пришла спустя пять дней. Пробыв в гавани Петропавловска-на-Камчатке полтора месяца и завершив там все дела по сдаче грузов, 6 сентября «Надежда» взяла курс к берегам Японии.
В пути, несмотря на ненастную погоду, Крузенштерн постоянно производил наблюдения и замеры, изучая морские течения и метеорологическую обстановку. Ни туманы, ни сильные ливни не могли помешать ему продолжать свою работу. Но самое худшее ожидало его при подходе к японским берегам.
Начался сильнейший тайфун. «Надежда» оказалась в опасности, ее могло опрокинуть в открытое море. Волны захлестывали палубу и надстройки, вода проникала даже во внутренние помещения, несмотря на то что люки были наглухо закрыты. И опять «Надежду» спасло лишь мужество ее команды. «Бесстрастие наших матросов, — вспоминал впоследствии Крузенштерн, — презиравших все опасности, действовало в сие время столько, что буря не могла унести ни одного паруса. В 3 часа полудни рассвирепела наконец оная до того, что изорвала все наши штормовые стаксели, под коими одними мы оставались. Ничто не могло противостоять жестокости шторма. Сколько я не слыхивал о тифонах (тайфунах), случающихся у берегов китайских и японских, но подобного сему не мог себе представить. Надобно иметь дар стихотворства, чтобы живо описать ярость оного».
Поднялся юго-восточный ветер, который погнал судно к скалистым берегам. «Надежда» опять оказалась на волоске от гибели. И лишь перемена ветра спасла судно.
В продолжение плавания от Камчатки к берегам Японии Крузенштерн исправил ранее существовавшие данные о положении Ван-Дименова пролива и вычислил точные координаты различных точек японского побережья. Этим точкам Крузенштерн присвоил наименования в честь деятелей и событий военной истории минувшего столетия: мыс Чичагова, мыс Чирикова, мыс Чесмы, мыс Кагула.
8 октября «Надежда» вошла в бухту главного города и порта острова Кю-Сю — Нагасаки. Здесь корабль простоял около четырех месяцев — то время, пока длились переговоры российского посольства с властями Японии.
Обратное путешествие Крузенштерн решил совершить вдоль Западного побережья Японии, несмотря на то что местные власти упорно убеждали отказаться от этого предприятия. Однако Крузенштерн также упорно желал попасть в пролив между Японскими островами и Кореей. Эта часть Тихого океана была известна лишь по описаниям Лаперуза, уже в то время считавшихся неполными и неточными. И он добился своей цели.
Крузенштерн определил точное местоположение острова. Цусимы, исправив ошибку Лаперуза, открыл и нанес на карту ряд пунктов на японском побережье, присвоив им названия: мыс Россиян, мыс Грейга и т.д., произвел подробное описание западного и северо-западного берегов острова Иессо (Хоккайдо).
Простояв несколько дней в бухте острова Иессо, которую Крузенштерн назвал Румянцевской, он повел «Надежду» через пролив Лаперуза к Сахалину. Там им было сделано описание восточного берега острова.
Дальнейший путь на север Крузенштерну преградили плавучие льды, и он взял курс на Курильские острова. По пути он открыл ранее неизвестные, но чрезвычайно опасные для моряков каменные острова. Они были небольшие и почти не выступали из воды. Нанося эти острова на карту, Крузенштерн назвал их Каменными Ловушками.
Прибыв на Камчатку, он высадил здесь российское посольство и взятый в Японии груз. Через две недели шлюп вновь направился к Сахалину и островам Курильской гряды.
Обследовав восточное побережье, Крузенштерн повел «Надежду» в Амурский лиман. По цвету и удельному весу воды Крузенштерн понимал, что совсем рядом должно было находиться устье Амура. Однако пройти к нему было невозможно, поскольку по мере приближения к берегу глубина резко уменьшалась и была опасность посадить «Надежду» на мель.
В конце августа шлюп вернулся на Камчатку для ремонта и пополнения запасов. В начале октября «Надежда» отплыла к берегам Южного Китая, где намечалась встреча с «Невой».
Встреча обоих шлюпов состоялась 3 декабря 1805 года на рейде Макао. Вскоре оба судна перешли в бухту Вампп вблизи Кантона.
В Кантоне Крузенштерну и Лисянскому пришлось решать и необычные для себя коммерческие задачи, однако и здесь они справились с порученным делом. Меха, лежащие в трюмах «Надежды» и «Невы», были выгодно проданы и вместо них туда перекочевали китайские товары — чай, фарфор и ткани. Крузенштерн внимательно изучил жизнь Китая и пришёл к выводу, что «благосостояние и покой китайцев есть ложный блеск, как обманывающий… Довольно известно уже, что число недовольных распространилось ныне по всему Китаю. Искра ко всеобщему возмущению таится».
В конце февраля 1806 года «Надежда» и «Нева» покинули берега «Небесной империи». Путь их лежал через Южно-Китайское море в Индийский океан, вокруг мыса Доброй Надежды в Европу.
После прохода через Малайский архипелаг, изобилующий многочисленными островами, шлюпы вошли в Зондский пролив, связывающий Яванское море с Индийским океаном. Здесь они попали в полосу штормов, из которой вышли лишь благодаря выучке команды и морскому искусству Крузенштерна и Лисянского.
В начале апреля «Надежда» и «Нева» оказались у мыса Доброй Надежды, где они попали в полосу густого тумана. Это привело к тому, что шлюпы вновь потеряли друг друга из виду. Однако оба капитана предвидели это обстоятельство и заранее наметили местом будущей встречи недавно открытый остров Святой Елены. Однако встречи с «Невой» здесь не произошло.
На острове Святой Елены Крузенштерн узнал о начавшейся войне между Россией и Францией, и это вынудило его принять соответствующие меры на случай встречи с кораблями противника. Положение осложнялось и тем, что часть корабельных орудий с «Надежды» была оставлена им на Камчатке на случай защиты поселенцев от нападения индейцев. Крузенштерн решил возвращаться На родину не Английским каналом — местом крейсирования французских военных кораблей, а двигаться в обход Великобритании с севера.
Пройдя этим маршрутом в относительной безопасности, «Надежда» в середине августа пришла в Кронштадтский порт, куда еще две недели назад вошла «Нева».
После возвращения на родину Крузенштерн стал готовить к публикации описание своего кругосветного путешествия. В 1806–1812 годах ему удалось издать его за государственный счет. Его сочинение было переведено на английский, французский, немецкий, голландский, шведский, датский, итальянский языки.