Посольство готовилось тщательно, целых три месяца, с самого момента отъезда из Петербурга посла Набиева. Данилевский должен был продолжить усилия Никифорова по определению границы России с ханством, проведя ее по реке Сыр, северному берегу Аральского моря и склону Усть-Урта. Одним из главнейших заданий миссии было составление и подписание формального торгового договора, которым русским предоставлялись права свободной торговли в Хиве, а русские купеческие караваны ограждались бы от набегов туркменских разбойников (всячески поощряемых хивинцами). Также Данилевскому было поручено вести переговоры об освобождении невольников, и в их числе полторы тысячи персов (об этом русских просило правительство Персии). Были даны посольству и секретные поручения. Они касались прежде всего ведения военно-топографической съемки не только пути до Хивы, но по возможности и самой Хивы, укреплений других городов и оазисов. Собственно, для этого и были к отряду прикомандированы военные топографы братья Зеленины. Конфиденциальная часть задания делала и без того непростую миссию дьявольски опасным предприятием. В Хиве понятие дипломатической неприкосновенности было весьма относительным. Поймай русских разведчиков хивинцы за сбором сведений, и тогда за жизнь всех участников посольства никто бы не поручился. История взаимоотношений с Хивой знала примеры, когда жизнь и смерть послов решались в зависимости от настроения вздорных властителей ханства.
1 августа 1842 года отряд Данилевского выступил из Оренбурга. Шли убыстренным маршем, невзирая на летнюю жару; на дневки не останавливались и многодневных привалов не устраивали; маршрут был таков: река Эмба, плато Усть-Урт и далее западным берегом Аральского моря. Вперед были посланы в Хиву гонцы, и, когда на 43-й день похода караван достиг пределов Хивинского ханства, на границе посла встретил почетный конвой, сопроводивший караван до Хивы, куда вошли 19 октября 1842 года. Миссию разместили в небольшом доме, стоявшем посреди сада; дом носил гордое название «дворца», хотя и состоял всего из нескольких комнат.
Отдохнув несколько дней, Данилевский стал добиваться встречи с ханом. Хивинский правитель несколько раз назначал и откладывал аудиенцию, и только 30 октября полковник, в сопровождении переводчика и ханского посланца в Петербург Набиева, оказался в покоях хана. Прием, оказанный Данилевскому, мало обнадеживал — хан был холоден и высокомерен.
Членов русской миссии представлял, называя чины и фамилии, казначей-мехтер. По протоколу восточной дипломатии первым делом были поднесены хану подарки. Он их принял, но даже не соизволил подойти к окну и взглянуть на ландо, поднесенное ему от имени русской короны. Хан сказал, что хочет вести переговоры, но не сейчас, а через некоторое время. Когда именно, он даст знать. На этом первая встреча Данилевского с ханом завершилась.
Посол убыл, огорченный холодностью и надменным тоном хана, и забыл приказать посольскому конюху, чтобы он объяснил придворным, как пользоваться ландо. Конюх же, опасаясь, как бы лошади не испортили торжественность официальной передачи подарка, взял да и поставил каретное колесо на тормоз. Когда же члены миссии, расстроенные приемом, удалились, он ушел вместе со всеми в посольский «дворец».
Между тем вокруг невиданного в Хива экипажа собрались чуть не все обитатели ханского дворца. Хан и его любимая жена сесть в ландо не решились. Для эксперимента сочли пригодными детей хана, усадили их и повезли по двору. Вернее, потащили, поскольку заторможенное колесо крутиться не хотело. Хивинцы о тормозах понятия не имели и поэтому решили пересилить строптивую повозку, добавив лошадей. Но тормоз был сработан на славу, и ландо еле двигалось. Так продолжалось, пока Данилевский не распорядился снова отправить конюха во дворец и тот все подробно растолковал тамошним служителям. После того как все тайны ландо были постигнуты, хан сел в открытый экипаж и торжественно проехал в нем по городу…
Покуда хан решал, когда он сможет вести переговоры, у русского посла началась дипломатическая рутина — прием гостей и сановников. Первыми с визитом прибыли восемь хивинских министров, заявившие, что пришли не по делам, а просто в гости. В переводе с языка восточной дипломатии это означало: «Подарки хотим получить». Гостей, приехавших верхами, в сопровождении мальчиков для услуг, провели в дом и принялись потчевать чаем. Чай подали в стаканах, и хивинцы не знакомые с этими предметами, пить не смогли и только обожгли себе руки. Тогда Данилевский как тактичный хозяин вылил свой чай в блюдце и стал прихлебывать его «по-купечески»; господа министры поспешили последовать примеру господина русского посла. В последующие посещения министров поили из чашек, которые посольство прикупило у Бочарова; среди его товаров всегда находилось все нужное для подарков: ситцы, трубки, ножи и прочее.