В те годы такое путешествие по диким и пустынным местам Османской империи было непростым, зачастую опасным. Воинственные бедуины часто нападали на паломников, тяжелы были бытовые условия. Только весной 1830 года, накануне Пасхи, Муравьев добрался до Святой земли. Он провел в Иерусалиме три недели, успел обойти все храмы и монастыри старого города и его ближайшие окрестности, где ступали Спаситель с апостолами: Гефсиманию, Вифанию, реку Иордан, на берегу которой, по словам самого Муравьева, «каждый стремился погрузиться в священные волны, каждый спешил зачерпнуть немного воды в принесенные меха и сосуды, и взять камень из средины реки, и срезать себе длинный тростник или ветвь ракиты на память Иордана…». Через Иорданскую пустыню Муравьев достиг Мертвого моря – еловом, повидал немало. Если бы тем дело и ограничилось, Андрей Николаевич стал бы одним из немногих в те годы русских паломников, но желание разделить с другими свою радость и поэтический талант подвигли его на описание своих странствий.
Путешествие в Палестину оказалось решающим этапом в жизни Муравьева. Судьба его определилась: отныне и до конца своих дней он служил Православной Церкви, хотя сам оставался в миру и продолжал вести светский образ жизни. Обозревая впоследствии свою жизнь, он писал: «…эта минута была самая решительная в моей жизни; в то мгновение не рассуждал я ни о чем и как бы внезапно посвятил себя и данный мне талант священной цели сего странствия, без всякого мудрования или каких-либо видов. Щедрою рукою вознаградил меня Господь, ибо все, что я ни приобрел впоследствии как в духовном, так и в вещественном, истекло для меня единственно из Иерусалима…».
Закончив в Москве написание первого варианта книги, Муравьев отправился на Троицкое подворье к митрополиту Филарету (Дроздову). Их познакомила в 1826 году духовная дочь владыки Е. В. Новосильцева, но тогда молодой аристократ был несколько обескуражен сдержанно-суховатым приемом. Вторая их встреча оказалась удачнее, и знакомство их утвердилось на долгие годы. Святитель Филарет, чрезвычайно загруженный делами своей епархии и присылаемыми из Святейшего Синода, а также иными обязанностями, поначалу отказался от просмотра рукописи, но Муравьев его упросил. Кроме митрополита, рукопись побывала в руках у В. А. Жуковского и цензора О. И. Сенковского, известного арабиста. Замечания и правка богослова, поэта и востоковеда способствовали большей точности описаний и красочности выражений. Книга «Путешествие по Святым местам в 1830 году» вышла в свет в 1832 году и сразу имела большой и шумный успех. Отныне и на всю оставшуюся жизнь Андрей Николаевич Муравьев стал
Среди многих путевых заметок по Ближнему Востоку и описаний паломничества, оставленных русскими писателями и литераторами, эта книга до сих пор выделяется искренностью чувства, живостью стиля и красочностью описаний. Вот рассказ о прощании Муравьева с Иерусалимом: «Наступил день отъезда, и с сжатым сердцем пошел я рано утром в Гефсиманию слушать литургию над гробом Богоматери, где я так радостно молился в день Благовещения; но хотя я сбирался в отечество, невозвратимая потеря святилищ палестинских раздирала мне душу. В последний раз перешел я обратно поток у горы Масличной, в последний раз прошел крестною стезею по Иерусалиму. Покамест все укладывали в моей келии, я ходил прощаться с духовенством; Наместник благословил меня в путь и, надев мне на шею малый крест на серебряной цепи с частицею Животворящего Древа, сказал: “Отныне будьте рыцарем Святого Гроба”.
Я просил отворить храм Воскресения. И там ожидали меня прощание с игуменом и братиею… но самое горькое было с великим Гробом. Я целовал его на вечную разлуку, как давнего друга, которого обнять из столь далеких краев устремился. Но я однажды достиг его, и отселе уже другая цель звала меня – Отчизна! На Голгофе, приникнув челом и устами к месту водружения Креста, молился я о моем счастливом возвращении и еще раз слышал Евангелие Креста над престолом страсти. Трудно было расстаться с сими залогами нашего спасения по чувству земной к ним любви и по слабости человеческой, которая невольно предпочитает для молитвы поприще священных событий, как бы ожидая на оном особенного внимания неба за одно лишь усердие потрудившейся плоти…