Наконец люди хана были готовы к отъезду, и более чем через два месяца после своего прибытия Муравьев опять отправился в пустыню. Среди огромной толпы, собравшейся поглазеть на его отъезд, он заметил махавшую ему вслед кучку русских с печальными лицами. Один мужчина, очевидно, благородного происхождения, какое-то время бежал у его стремени и умолял не забывать «нас, несчастных». Вдоволь намерзшись в пустыне, 13 декабря 1819 года они наконец достигли Каспия. Муравьев с огромным облегчением увидел, что доставивший его русский корвет все еще стоит на якоре неподалеку от берега. Чтобы привлечь внимание, он водрузил на шест свою шляпу, и за ним тут же была отправлена шлюпка. Его благополучное возвращение вызвало огромную радость, но он узнал, что за пять месяцев, прошедших с момента их выхода из Баку, команде довелось перенести неимоверные страдания. Из ста двадцати человек только двадцать были в состоянии нести службу. Пятеро умерли, тридцать болели цингой, остальные были так истощены, что с трудом могли передвигаться по палубе.
В Баку они вернулись перед Рождеством. Там Муравьев узнал, что генерал Ермолов находится в Дербенте, дальше по побережью, и немедленно направил командующему рапорт о своем благополучном возвращении. Генерал отдал приказ переправить хивинских послов в Тифлис, где намеревался их принять. Муравьев тем временем засел за составление полного отчета о своей миссии, включив в него свои рекомендации на тот счет, что следует предпринять, чтобы освободить подданных царя из рабства. В отчете содержалось все, начиная от оценки возможностей ханской армии, слабости его оборонительных сооружений, размеров его арсеналов и лучших подходов для наступающей армии до экономики, системы управления, преступности, системы наказаний, пыток и способов казни (из которых самым предпочтительным было сажание на кол). Еще Муравьев описал «ужасную жестокость» хана и его склонность к придумыванию новых способов пыток и истязаний. Тем, кого ловили за выпивкой или курением, которые запретили после того, как от них отказался сам хан, разрезали рты до ушей. Возникавшая от этого постоянная жуткая гримаса должна была служить мрачным предупреждением для других.
Муравьев страстно призывал к скорейшему завоеванию Хивы. Это не только освободит русских из рабства, но и положит конец тирании, в условиях которой вынуждено жить подавляющее большинство ханских подданных. Более того, обладание Хивой позволит России сломать британскую монополию на бесценную торговлю с Индией. Когда Хива окажется в руках русских, «всю торговлю Азии, включая и индийскую», можно перенаправить через Каспий и дальше по Волге в Россию, а потом на европейские рынки. Такой путь представлялся куда короче и дешевле, нежели вокруг мыса Доброй Надежды. Это серьезно подорвет, а может быть, даже и разрушит британское правление в Индии и одновременно обеспечит крайне необходимые для русских товаров рынки как там, так и в Центральной Азии.
Более того, Муравьев утверждал, что завоевание Хивы не станет ни трудным, ни дорогостоящим предприятием. Он полагал, что оно может быть совершено «решительным командиром, стоящим во главе всего трех тысяч храбрых солдат». Армия вторжения очень быстро встретит поджидающих ее ценных союзников. Для начала ими стали бы воинственные туркменские племена, кочующие в пустыне, которую предстояло пересечь, чтобы достичь Хивы. Исходя из собственного опыта, Муравьев ручался, что они также смертельно боятся хана, как и его собственные подданные, и охотно присоединятся к любому, кто вознамерится его свергнуть. В самой столице захватчик сможет воспользоваться яростной поддержкой многочисленной пятой колонны. Кроме 3000 русских рабов, многие из которых прежде
Несмотря на все опасности, с которыми столкнулся Муравьев, собирая разведывательную информацию для своих начальников, его грандиозный план захвата Хивы и освобождения русских и других рабов не привлек внимания. Момент был упущен, поскольку когда-то великий Ермолов начал медленно терять расположение царя, что закончилось его смещением с должности военного губернатора Кавказа. У самого царя Александра хватало более насущных проблем, с которыми ему пришлось столкнуться дома, где его положению угрожали недовольство и неприязнь. Тем не менее Муравьев смог по крайней мере сдержать обещание, данное несчастным русским при отъезде из Хивы. Вызванный в Санкт-Петербург для награждения за храбрость, он подал самому царю краткую записку о судьбе его подданных в Хиве. Даже если Муравьев не имел возможности как-то ускорить их освобождение, его разоблачения могли послужить русским великолепным предлогом для дальнейшей экспансии в мусульманскую Центральную Азию. Таким образом, его путешествию было предназначено судьбой обозначить начало конца независимых центральноазиатских ханств.