Наступил 1838 год. Бутакова перевели служить с «придворного», как он выражался, фрегата «Кастор», обслуживавшего царский двор, на пароходо-фрегат «Богатырь». Это чудо техники, с огромными гребными колёсами и густыми клубами дыма из трубы, было первым паровым фрегатом, построенным в России. Плавать на нём было мучение: запас угля маленький, а топлива машина пожирала много, поэтому только и занимались погрузкой угля. На верхней палубе всё вечно было в копоти и саже. Постоянно приходилось отмывать и отскребать палубу и надстройки, к тому же у офицеров и матросов из-за дыма и летевшей сажи часто развивались болезни глаз. Очки с металлической сеткой, заменявшей стёкла, которые выдали личному составу, не защищали от мельчайшей угольной золы. Тем не менее тогда это было новейшее судно, и служба на нём считалась очень почётной. Назначению на «Богатырь» Бутакову поспособствовал бывший командир, капитан-лейтенант Андрей Логинович Юнкер, который, как писал родителям Алексей, «во-первых, сделал из меня порядочного морского офицера, а, во-вторых, накричал обо мне весьма и каждому, что я только звёзд с неба не хватаю».
Приобретённый опыт службы на пароходе пригодился ему много позже, только тогда молодой моряк даже в страшном сне не мог представить, при каких обстоятельствах это случится. Пока Алексей осваивал службу на балтийских кораблях, произошло немало семейных событий. Окончил Морской корпус Григорий и даже успел заработать на Чёрном море первую боевую награду, заканчивал учёбу в корпусе брат Иван, которого он всегда навещал, бывая в Петербурге, подошла очередь Дмитрию и Владимиру становиться кадетами.
Алексей написал письмо Григорию, спрашивая, стоит ли ему добиваться перевода в Черноморский флот. Брат категорически отсоветовал это делать, упирая на то, что заниматься литературной работой, к которой Алексей имел склонность, в Черноморском флоте у него не будет возможности. Я много раз перечитывал это письмо, роковым образом сказавшееся на судьбе Алексея, пытался понять истинные мотивы Григория. Может быть, тому не хотелось стать на флоте вторым? Правда, пока служил отец, тот был Бутаковым 1-м, но у отца пенсия была уже не за горами. В 1840 году для доставки грузов на Камчатку предстояло отправиться военному транспорту «Або». По традиции командиру предоставлялось право самому выбрать себе старшего офицера. Командиром транспорта назначили Юнкера, и он, высоко ценя служебные качества Алексея Бутакова, предложил его кандидатуру, которая и была утверждена В ту пору дальние плавания случались редко, попасть в них считалось большой удачей. Не только потому, что моряки приобретали бесценный опыт, — это был отличный старт для дальнейшего карьерного роста По окончании кругосветки, как правило, щедро раздавались орденские и денежные награды, длительные отпуска И, без всякого сомнения, всё это вполне заслуженно и справедливо, потому что каждое подобное плавание для его участников было суровым экзаменом на прочность. Иногда судна попросту исчезали без следа О том, что с ними случилось, можно только гадать — моря и океаны надёжно хранят свои тайны. Контр-адмирал Иван Николаевич Бутаков, узнав о назначении сына, приехал из Николаева в Петербург, чтобы попрощаться с Алексеем перед кругосветным плаванием, дать ему последние советы и напутствие.