Не впустую пропали усилия пламенного полемиста, заработавшего в Европе славу «главного защитника Русской Церкви и давнего врага Церкви Католической». В эти годы на Западе возрастает интерес к незамечаемой ранее Православной Церкви, одним из показателей которого во Франции стал переход в Православие католического священника Владимира (Рене-Франсуа) Геттэ, тут же запрещенного в служении, а книги его были внесены в Индекс запрещенных книг. Кстати, и барона Гакстгаузена в Риме заподозрили… Папский нунций в Мюнхене Флавио Киджи предупреждал: «Есть все основания полагать, что он – русский агент или, по меньшей мере, инструмент в делах русских».
Путешественник справедливо считал себя преимущественно церковным писателем, его драматические произведения не имели успеха у публики. Однако все же Муравьев оказал важную услугу русской литературе… своим отсутствием. В один зимний день, 18 февраля 1837 года, на квартиру к Муравьеву зашел его знакомый, поручик М. Ю. Лермонтов, надеявшийся на помощь влиятельного сановника в публикации своего стихотворения на смерть Пушкина. Хозяина не было дома. Лермонтов в ожидании зашел в образную, где увидел между икон ваии – плетеные пальмы, употребляемые в Иерусалиме при крестных ходах на празднике Входа Господня в Иерусалим (на Вербное воскресенье). Он так и не дождался Муравьева в тот день и ушел, оставив на столе исписанный лист бумаги. То были дивные стихи «Ветка Палестины»:
Скажи мне, ветка Палестины:
Где ты росла, где ты цвела?
Каких холмов, какой долины
Ты украшением была?..
Прозрачный сумрак, луч лампады,
Кивот и крест, символ святой…
Все полно мира и отрады
Вокруг тебя и над тобой.
В 1840 году выходит новая книга Муравьева «Первые четыре века христианства». Это не столько научный труд, сколько сердечно и проникновенно написанная православным человеком повесть о Матери-Церкви, о том, как возникла она в 33 году, как пережила жесточайшие гонения и смуты ересей, как вызвала к жизни сонмы мучеников за веру и великих апологетов – защитников веры, мудрых богословов и пламенных проповедников. Стоит заметить, что в своей работе Муравьев, конечно же, использовал различные труды Отцов Церкви и исследования по истории Церкви, однако его книга не подавляет ученостью, она написана живо, простым и ясным языком.
В 1842 году Андрей Николаевич подает в отставку и оставляет Святейший Синод. Причиной тому послужило удаление из Синода митрополита Филарета (Дроздова) из-за возросших разногласий с обер-прокурором Н.А. Протасовым. Тем не менее Муравьев остался на государственной службе, он был причислен к Азиатскому департаменту Министерства иностранных дел, что было не слишком обременительно и оставляло ему довольно времени на написание книг.