После событий Персидской войны 1804–1813 годов русской военной элите стало ясно, что недооценивать коварство англичан опасно, и при этом было очевидно, что столкновение интересов двух империй уже произошло. Формально главой экспедиции был Елизаветпольский окружной начальник майор Пономарев, капитан Муравьев был представителем Генерального штаба, то есть, говоря прямо, именно он был настоящим разведчиком. 28 июля 1819 года экспедиция высадилась на туркменских берегах Каспийского моря. В течение полутора месяцев Муравьев обследовал побережье, составлял карты, общался со старейшинами туркмен-иомудов, уговаривал их сопроводить его в Хиву. И 19 сентября Муравьев в сопровождении денщика и отрядного переводчика-армянина вместе с небольшим отрядом туркменов отправились к заданной цели.
«Во все время поездки моей ходил я в Туркменском платье и называл себя Турецким именем Мурад-бек; сие имело для меня значительную выгоду потому, что хотя меня и все в керване знали, но при встречах с чужими я часто слыл за Туркмена поколения Джафарбай и тем избавлялся от вопросов любопытных».
Правда, в какой-то момент Муравьев едва не погиб. Встреченные туркмены поняли, что перед ними в составе каравана едут русские.
Впрочем, до Хивы экспедиция добралась без приключений. 5 октября Муравьев собирался въехать в город, но был остановлен сановниками ханского двора, посольству было назначено дожидаться приема в небольшой крепости Иль-Гельды. Более месяца Муравьев был, по сути, в положении пленника. Хан никак не мог понять, что ему делать – убить русского, но тогда возможно, что русские пришлют сюда войска. Принять русского? Но как это будет воспринято в Бухаре, и вообще, зачем этот русский сюда приехал? Каждый день Муравьев ожидал, что его казнят. Только утром 16 ноября было наконец получено приглашение хана, и на следующий день Муравьев въехал в Хиву. Ему тут же нанесли визиты высшие чиновники – начальник таможни, первый визирь и диван-беги, то есть премьер-министр. 20 ноября Муравьева принял хан. Ему были вручены подарки от Ермолова, а Муравьев объяснил, что российский император хотел бы развития взаимовыгодной торговли между обеими странами, что послужило бы их процветанию.
Но хан прямо не ответил ни на одно предложение и сказал, что отложит решение этого вопроса до прибытия хивинского посольства на Кавказ. А именно это предложил ему Муравьев. И оно действительно было послано, сам же Муравьев в своих записках подробнейше описал свое пребывание в Хиве, нравы и быт, и особое внимание он уделил проблеме русских рабов. Жизнь этих людей, условия, в которых они находятся, Муравьева ужаснули.