Капитану предстояло, переодевшись кочевником, проделать восемьсот километров через пустыню, чтобы передать послание губернатора Хивинскому хану. И это несмотря на недавнее предупреждение от южного владыки, что любой русский, который окажется во владения Хивинского ханства будет немедленно казнен. Неверных в Хиве не любили, ну разве что в качестве рабов. Но империя нуждалась в налаживании торговли с далеким ханством, также как и в прекращении набегов кочевников на свои южные границы, и ради этого стоило рисковать.
Месяц капитан провел в туркменских кочевьях, пока ему не удалось договориться с одним из племен, что он присоединиться к их каравану, идущему в Хиву. Было решено, что он будет путешествовать под видом туркмена Мараг Бега. И, хотя люди в караване знали, что он русский, за сорок золотых монет они согласились закрыть на это глаза. И все же опасность разоблачения была очень велика, и поэтому молодой офицер не расставался с парой пистолетов спрятанных под одеждой. Наконец, в конце сентября, когда жара начала немного спадать, а ночи стали прохладными, караван тронулся в путь. С собой Муравьев взял двоих: переводчика и проводника туркмена, по имени Сеид.
Поход через пустыню проходил без особых происшествий, не считая паразитов которые прямо таки кишели в одежде. Днем, одежду клали на раскаленный песок, но это мало помогало. Вдобавок, вся одежда пропиталась запахом пота и дымом костров, но Муравьеву, привыкшему к воинским тяготам, это не доставляло особых неудобств. Он был полон впечатлений от увиденного, и по вечерам, тайком, вел дневник, куда записывал все увиденное за день.
Но, когда до Хивы осталось всего пять переходов, счастье изменило капитану. В этот день они ушли с дороги, пропуская большой, в тысячу верблюдов караван, и один из купцов, видавший его мельком в Баку, узнал его, указав на него пальцем. О чем он говорил, Муравьев не слышал, но страх мерзким холодком разлился по его жилам. Другие торговцы и погонщики подошли к туркменам из его каравана и напрямую спросили кто он такой. Но глава каравана, как ни в чем не бывало заявил: что дескать да, он пленный русский и они везут его на продажу в Хиву. Торговцы заулыбались и закивали головами, в знак одобрения. Один из них сообщил, что сам недавно продал двух русских за хорошую цену. На этом инцидент был исчерпан и через пять дней на горизонте, наконец, показались белые стены и голубые минареты Хивы.
Остановившись в ближайшем к Хиве караван-сарае, капитан послал двух человек впереди себя, дабы известить хана и местное начальство о своем прибытии в качестве российского посла. Между тем он, наконец-то, тщательно умылся и переоделся в свой парадный мундир, чтобы предстать перед хивинцами как официальное лицо. Через несколько часов к караван-сараю подъехали двое всадников в богато расшитых халатах. Один из них - низкий, с обезьяньей мордочкой под большой белой чалмой, а второй - высокий и дородный, с рыжеватой бородой. Главным оказался высокий, который представился офицером ханской армии. Он и сообщил русскому послу, что хан примет его завтра, а пока попросил его подождать в небольшой крепости неподалеку, где, как он заверил, капитану будет оказан соответствующий восточному гостеприимству прием.