В августе 1869 года Александр II, основываясь на докладах министра и Столетова, утвердил предположения «О Красноводской экспедиции». Вначале хотели назначить начальником отряда генерал-майора Геймана, а Столетова начальником штаба. Но главнокомандующий Кавказской армией великий князь Михаил Николаевич решил иначе:

– Командование отрядом полагаю поручить полковнику Столетову как по его способностям и знанию, так и потому, чтобы назначением генерала не вспугнуть англичан!

– Не возражаю! – согласился император. – Столетов умен и храбр. Ему и карты в руки!

Не возражал против кандидатуры Столетова и военный министр.

Экспедиция должна была занять берег Красноводского залива и пункта в Балханских горах, причем о посылке русского военного отряда персов решено было уведомить заранее.

Выступление отряда было назначено на осень 1869 года. Задачи Столетову были поставлены так: «В случае образования враждебной нам коалиции среднеазиатских владетелей или необходимости поддержания принесшего нам покорность бухарского эмира, вновь занятый нами пункт может служить исходною точкою и базою отряду, переброшенному через Каспийское море, для совокупных операций кавказских войск с войсками Туркестанского округа. Наконец, в случае установления движения караванов между Красноводском и хивинскими владениями, торговый путь к некоторым рынкам Средней Азии значительно будет сокращен и удешевлен».

– Твоя задача – подготовить будущее генеральное наступление на Хивинское ханство! – сказал напоследок Столетову Милютин.

– Я готов сие генеральное наступление и осуществить! – гордо ответил Столетов.

– Ну, об этом мы подумаем чуть погодя! – охладил пыл подчиненного министр.

Переправа отряда через Каспийское море была организована безукоризненно. Впрочем, как писал позднее Столетов: «Из-за противных ветров и сильного волнения, замедлявших ход шхун», до пункта назначения добрались только 5 ноября. Через два дня полковник сообщил главнокомандующему Кавказской армией: «Отряд в сборе, здоровье людей хорошо, все необходимое с нами. Полковник Столетов».

Одновременно с отплытием отряда из Петровска новый российский посол в Тегеране Бегер прибыл с визитом к министру иностранных дел Персии Мирзе Саид-Хану и заявил:

– Русская экспедиция в Красноводский залив не имеет никакого враждебного характера ни к Персии, ни к туркменским племенам, а предполагает целью освоение фактории, которая могла бы служить как средством для продолжения торгового пути в Среднюю Азию, так и наблюдательным постом за сношениями хивинцев и туркменами.

– Есть ли у вас официальный документ?

– Документ имеется! – кивнул Бегер и вытащил из кожаного портфеля бумагу.

– Вот телеграмма от моего министра иностранных дел.

– Что же там написано? – полюбопытствовал перс.

– Его императорское величество признает владычество Персии до Атрека и не имеет в виду никаких укреплений в этой местности!

Мирза Саид-Хан выслушал Бегера, огладил бороду и сделал вид, что поверил. Сообщение Горчакова понравилось и Насреддин-шаху, который разрешил российским пароходам отныне входить в порты Муграб и Энзели наравне с парусными судами, чего Россия давно добивалась.

Итак, Красноводский отряд, состоявший из тысячи солдат при тридцати офицерах, спокойно высадился на берегу Красноводского залива в Муравьевской бухте.

Начальником этнографо-статистического отдела экспедиции являлся полковник Леонид Соболев (будущий премьер-министр Болгарии), художником экспедиции – герой Самаркандского похода отставной капитан Каразин, а в научную группу вошел будущий знаменитый исследователь Средней Азии Северцов. В отряде был и знаменитый в будущем штабс-капитан Михаил Скобелев.