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