«Все почти карты рисованы сим последним искусным офицером, который в то же время являет в себе способность хорошего гидрографа; он же составил и генеральную карту».
Кругосветное плавание продолжалось три года (1803–1806). По возвращении из него Беллинсгаузен в чине капитан-лейтенанта был назначен командиром фрегата Балтийского флота, а в 1810 году переведен на Черноморский флот.
В продолжение многих плаваний вдоль Черноморского побережья Беллинсгаузен не раз обращал внимание на то, что карты недавно присоединенных земель Абхазии, Мингрелии и Гурии содержат массу неточностей. Летом 1816 года он составил собственную карту этих мест. Широту ее основных пунктов он определял с помощью астрономических наблюдений с берега, а долготу, пользуясь хронометром. Последующие наблюдения подтвердили правоту Беллинсгаузена, и скоро он завоевал репутацию лучшего гидрографа Черноморского флота.
Шлюп Беллинсгаузена построил англичанин В. Стоке, о котором командир «Востока» отзывался достаточно резко, как о главном виновнике того, что шлюп фактически непригоден для плавания.
«Восток» — трехмачтовый корабль водоизмещением 450 тонн — был сооружен из сырого соснового леса и не имел дополнительных креплений корпуса. Мачты и реи, т.н. рангоут были необычайной величины, верхняя часть руля — румпель также была ненадежной, а это грозило привести к потере управления кораблем.
В целях укрепления «Востока» подводная часть его корпуса была скреплена и снаружи обшита медью.
Были предприняты меры и по сохранению здоровья членов команды. Сам Беллинсгаузен составил инструкцию о порядке содержания жилых помещений на корабле, о мытье людей, чистоте коек и белья. В целях предохранения команды от цинги были сделаны запасы хвойной эссенции и кислой капусты.
Незадолго до выхода в плавание Беллинсгаузен получил инструкцию, в составлении которой принимал непосредственное участие Крузенштерн. Инструкция обобщала весь опыт дальних путешествий и теперь ставила перед Беллинсгаузеном задачу обнаружить антарктический материк. В ней говорилось: «Идти там к северу, где Кук шел к югу, идти к югу там, где Кук шел к северу».
В 6 часов утра 4 июля 1819 года отряд Беллинсгаузена в составе шлюпов «Восток» и «Мирный» снялся с рейда Кронштадтского порта.
Спустя десять дней шлюпы подошли к рейду Копенгагена, с которого они должны были взять на борт двух немецких натуралистов — Мертенса и Кунца. Незадолго до выхода в плавание Беллинсгаузен попытался протестовать против этого распоряжения, доказывая, что в самой России немало специалистов, которые сочли бы за честь участвовать в первой антарктической экспедиции.
Вскоре выяснилось, что немецкие ученые не решились пуститься в плавание, сочтя его достаточно рискованным. Вот почему натуралистов на шлюпах не оказалось и впоследствии Беллинсгаузен говорил, что для науки гораздо больше пользы было бы, если на борту «Востока» и «Мирного» оказались хотя бы два русских студента.
Несколько дней шлюпы простояли у берегов Англии, а затем направились к Канарским островам. 15 сентября «Восток» и «Мирный» бросили якорь у города Санта-Крус. Здесь Беллинсгаузен еще раз провел активную подготовку членов экипажей к плаванию в высоких широтах. Офицеры изучили все имеющиеся данные, относящиеся к будущему району своих исследований.
2 ноября шлюпы подошли к Рио-де-Жанейро, где встали на якорь возле Крысьего (Фискального) острова. Здесь были произведены последние приготовления перед отправкой в Антарктику — приведены в порядок наружное вооружение, такелаж, проверены обшивка и корпус шлюпов. Утром 22 ноября шлюпы покинули Рио-де-Жанейро.
Карты этого времени не всегда достаточно точно отражали настоящее положение береговой линии, островов, подводных камней и рифов. Так, после 45-й параллели Беллинсгаузен ожидал увидеть остров Гранде, который, по некоторым сведениям, открыл в 1675 году французский путешественник Ха-Рош, однако этого острова в действительности не оказалось, и Беллинсгаузен понял, что французский мореплаватель допустил ошибку в счислении.
При подходе к острову Южная Георгия уже чувствовалось приближение Антарктики, температура воздуха заметно понижалась, в море стали попадаться айсберги.
Недалеко от острова Южная Георгия участники экспедиции обнаружили небольшой остров, который назвали именем одного из участников экспедиции Анненкова. Скоро шлюпы подошли к неизвестному ранее архипелагу и дали его островам имена других участников экспедиции: Завадовского, Лескова и Торсона.