Прибыв в Стамбул, Воробьев должен был явиться к российскому посланнику барону Григорию Александровичу Строганову и показать ему полученные инструкции лично. Раскрывать кому-то другому свои планы и суть порученной ему миссии художнику дозволялось только с разрешения барона Строганова. Помимо инструкций А. Н. Оленин снабдил Воробьева рекомендательными письмами. Одно из них было адресовано другу Оленина, российскому генеральному консулу в Измире, Спиридону Юрьевичу Дестунису. Это письмо должно было помочь в организации поездки Воробьева в Палестину.
В конце апреля 1820 г. М. Н. Воробьев прибыл в Стамбул. Там, в российском посольстве в Буюк-дере, нашли замечательное решение, обеспечившее художнику режим наибольшего благоприятствования в выполнении его важной, но неофициальной миссии. Еще в январе 1820 г. второму советнику посольства Дмитрию Васильевичу Дашкову было поручено министром иностранных дел «обозрение и приведение в надлежащее положение российских консульств в Леванте». В рамках выполнения своих служебных обязанностей Д. В. Дашков организовал инспекционную поездку, к которой присоединился М. Н. Воробьев.
Подготовка путешествия и различные согласования заняли около двух месяцев. Только в конце июня художник отплыл из Стамбула в Измир, где его ожидал Д. В. Дашков. Из Измира они направились на Родос. Продолжительные остановки, встречные морские течения и слабые ветра, иногда сменявшиеся полным штилем, сделали путешествие небыстрым. Лишь 2 сентября 1820 г. корабль, на котором плыла миссия, бросил якорь на рейде Яффы.
Проживавший постоянно в Стамбуле Иерусалимский Патриарх Поликарп снабдил миссию своей грамотой, и путешественники везде встречали самый теплый прием со стороны греческих монахов. С готовностью помогали дипломатической миссии и местные власти, опасавшиеся вызвать своей нерасторопностью неудовольствие скорого на расправу Абдуллы – нового паши Акко, державшего под своим контролем всю Палестину. Яффский губернатор выделил миссии сопровождающих – для охраны и, главным образом, для того чтобы арабские шейхи, включая знаменитого шейха Абу-Гоша, не требовали с путешественников подорожные сборы, от которых российские подданные были официально освобождены по Кючук-Кайнарджийскому мирному договору. Переночевав в греческом монастыре в Яффе, миссия выехала вечером 3 сентября в Иерусалим.