Совместно с Игнатьевым Бутаков участвовал в разработке плана и в снаряжении посольства Ему присвоили пышный титул начальника Аральской флотилии. Правда, такое название должности обещало и повышение оклада жалованья. Обговорив с начальством все вопросы, Алексей Иванович вместе с женой в марте возвращался в Оренбург. И, надо же такому случиться, вот уж поистине мир тесен: на почтовой станции во Владимире они встретили Тараса Григорьевича, который уже давно простился с оренбургскими степями. Прошло восемь лет со времени их последней встречи, а кто старое помянет, тому глаз вон! В письмах друзьям Шевченко вспоминал о Бутакове тепло: «Это мой друг, товарищ и командир…» Да и что иного он мог сказать о человеке, который так хорошо к нему отнёсся? Неизвестно, испытывал ли к нему такие же тёплые чувства Алексей Иванович, но всё дурное со временем забывается, а помнится только хорошее. Их связывали общие воспоминания об экспедиции, где обоим пришлось пережить всякое. Беседовали они долго. Бутаков рассказал, что едет с женой в Оренбург, а затем он уже один отправится на Сырдарью. Ольга Николаевна была наслышана о Шевченко и от мрка, и от знакомых в Оренбурге и Петербурге, видела его работы. Сама талантливая художница, она по достоинству оценила картины, написанные Тарасом Григорьевичем.
Некоторые исследователи творчества Шевченко утверждают, что Ольга Бутакова позднее сделала по ним прекрасные офорты. Сохранила она, понимая их ценность, и некоторые картины Тараса Шевченко, находившиеся в материалах экспедиции на Арале, и за одно это благородное дело заслужила, чтобы остаться в памяти потомков. Бывшие сослуживцы расстались, чтобы больше никогда не увидеться. Тарас Григорьевич записал в своём дневнике об этой встрече: «…У меня при одном воспоминании об этой пустыне сердце холодеет, а он, кажется, готов навсегда там поселиться». Насчёт слов поэта о готовности Бутакова навсегда там поселиться, конечно, некоторое преувеличение, позволенное творческой личности. Но то, что для одного из них было ссылкой, для другого — местом службы отечеству. К тому же на здоровье Алексея Ивановича не могли не сказаться плавание на «Або» и жизнь на Арале и в степях и песках Средней Азии. 15 мая 1858 года миссия в сопровождении конвоя и обоза двинулась в путь из Оренбурга к Аральскому морю. Бутаков уехал туда раньше. Ему предстояло подготовить суда для плавания.
В распоряжение Алексея Ивановича прислали опытных офицеров, участников экспедиции вице-адмирала Ефима Васильевича Путятина и 80 человек матросов и унтер-офицеров из 45-го астраханского флотского экипажа. Сборкой судов занимались мастеровые с Боткинского завода. Собралась компания моряков, побывавших в разных жизненных переплётах, им было о чём рассказать друг другу, тем более что все знали братьев Бутаковых. Алексей Иванович разместил участников посольства на пароходе «Перовский» и на двух железных баржах. Лейтенанту Александру Фёдоровичу Можайскому он поручил командовать одной баржой, а другой — лейтенанту Александру Александровичу Колокольцеву.
Удобства для жизни на баржах и пароходе были не из тех, которым стоило завидовать, да ещё в условиях азиатской жары. Но что поделаешь, приходилось терпеть, и не такое видели. По ряду причин отправились позже, чем намечали, и, когда подошли на судах к устью Амударьи, оно уже обмелело, что создало дополнительные трудности. Гигантские камыши, которыми поросли не только все отмели, но и дно на глубине до трёх метров, можно было сравнить только с джунглями. Тучи комаров как будто специально сидели на голодной диете, дожидаясь появления русских. Впрочем, в камышовых зарослях можно было встретить не только комаров, но и других живых существ, покрупнее, включая тигров. Хивинское правительство сразу раскусило истинные намерения посольства и отказалось пропустить суда в Амударью. Начались длительные изматывающие переговоры Игнатьева с хивинским ханом Они осложнились из-за того, что хану стало известно о съёмках местности, проводившейся под руководством Бутакова. Кроме того, хивинцы посчитали вмешательством в свои внутренние дела отказ Алексея Ивановича выдать укрывшегося у него на пароходе беглого раба, перса. Бывшему владельцу раба капитан 1-го ранга заплатил выкуп из личных денег, но всё равно это вызвало большое недовольство у хивинцев. Тем не менее, пока Игнатьев вёл переговоры, Бутаков продолжал вести подробные исследования от низовьев Амударьи до Кунграда Несмотря на запрещение хивинских властей, он вошёл в Кунград, чтобы облегчить положение посольства, которому уже явно начинали угрожать.
То, что Бутаков сумел довести пароход до Кунграда, не посадив его на мель, было просто чудо. Обычная глубина в тех местах не превышала брюха лошади. Ситуация складывалась непростая не только для Игнатьева, но и для Бутакова Запас угля у него был ограниченный, оставалось около семисот пудов. Остальной находился на барже у Колокольцева, но тот не мог передать уголь на пароход по навигационным условиям. Топить паровой котёл было нечем, поскольку на берегу росли только фруктовые деревья, рубить которые Бутаков никогда бы не решился, прекрасно понимая последствия такого поступка Задерживаться в Кунграде было нельзя. В случае ещё большего понижения уровня воды пароход оказывался в ловушке, Бутакову тогда пришлось бы там зимовать без продовольствия, а, учитывая настроение хивинцев, их могли попросту уморить голодом. Посовещавшись, Игнатьев и Бутаков решили, что пароход отправится к Сырдарье, где находился русский порт. Колокольцеву поручили доставку продовольствия для посольства Можайскому, на барже которого находились вьючные лошади и верблюды, Бутаков приказал сдать баржу лейтенанту Зеленину, а лошадей и верблюдов берегом доставить Игнатьеву. Тот собирался направиться в Бухару, и у него имелись серьёзные опасения, что хивинцы не дадут ни лошадей, ни верблюдов. Убедившись, что посольство Игнатьева обеспечено всем необходимым, Бутаков взял на буксир обе баржи и перешёл в форт №1. Можайского Игнатьев оставил при себе в составе посольства
Из Хивы посольство Игнатьева двинулось караваном в Бухару. Здесь ему удалось добиться полного дипломатического успеха, играя на противоречиях между двумя среднеазиатскими правителями. На следующий год, следуя по обследованному пути, Алексей Иванович участвовал в боевых действиях на Амударье. Погрузив на свой пароход сто сорок человек десанта, он подошёл к Кунграду, который осаждали хивинские войска Появление русского десанта заставило хивинского хана снять осаду Кунграда Затем на паровом баркасе «Обручев» Бутаков дважды прошёл мимо хивинской крепости Нукус. Видимо, это было непросто и очень важно для русских, потому что этот, вроде бы совсем незначительный, эпизод особо отмечен в его послужном списке. На Новый год Бутакова назначили в свиту императора Приказ об этом подписан 1 января 1860 года Он получил звание флигель-адъютанта Помимо почётной приставки к морскому званию, увеличивалось и денежное содержание, добавлялись «свитские». По результатам проведённой Бутаковым операции Военное и Морское министерства пришли к общему выводу о том, что необходимо наращивать морские силы на Арале. Для этого прежде всего требовались суда
На этот раз Бутакову вручили приказ ехать в Англию для заказа железных пароходов, плавучего понтонного дока и барж. Ну и, слава богу, появилась возможность не видеть некоторое время ни вечно мутных вод Амударьи, ни вечно синих — Аральского моря. Из Англии его направили в Соединённые Штаты. Вырваться, хоть и на время, из Тмутаракани в цивилизованные страны была большая удача. По результатам своей командировки Алексей Иванович опубликовал в «Морском Сборнике» статью о пароходах с небольшой осадкой, у которых колесо находится в кормовой части. Задумаешься, что было легче и дешевле: организовать производство пароходов, скажем, на Боткинском заводе или везти их из заморских стран? Но, как сказал великий грузинский поэт: «Каждый мнит себя стратегом, видя бой со стороны», — наверно, тогда считалось выгоднее купить за рубежом. Перевозка обошлась в солидную копеечку. Если бы это происходило в наше время, то все участники и посредники такого оборонного заказа просто обогатились бы.
Вообще то, воровали и в те времена. Разница с нынешними — только в масштабах. Но, несмотря на то, что пароходики стали буквально золотыми для казны, на благосостоянии Алексея Бутакова это никак не отразилось, не был Алексей Иванович казнокрадом, так же, как и его отец и все братья. Не передать, каких нервов ему стоила доставка заказанных судов. Их сплавляли по Волге до Казани, а затем пришлось перегружать на телеги и верблюдов и тащиться по грязи в степях, раскисших от небывалых в тех краях проливных дождей. Дорог не было, остались только направления. Стояла поздняя осень, и скоро ливни сменились морозами и метелями. Вместе с Алексеем Ивановичем была и Ольга Николаевна. Всё-таки замечательные жёны были у русских морских офицеров! Чего им только не доводилось испытать. Вот уж вправду о них можно было сказать: «Есть женщины в русских селеньях..» Сначала груз, а он представлял собой свыше шести тысяч пудов железа, везли на телегах, потом переложили на сани. Зима началась очень рано. 30 сентября был буран при 8 градусах мороза. Но все части пароходов доставили в Оренбург благополучно, а вот с личными вещами семейства Бутаковых оказалось хуже — они остались в степи, занесённые снегом. Кое-что потом всё же удалось спасти. Часть животных погибла, и Алексей Иванович приказал своё имущество бросить, а вести казённый груз. Один только этот переход по морозной степи можно считать подвигом всех, кто сопровождал караван.
