Нечаев и далее не останавливался грешить против совести. Он стал представлять на утверждение Императору кандидатуры архиереев, не указанных в записке членов Синода. Подлог не мог сойти с рук, синодалы искали случая избавиться от лгуна. И случай такой представился: летом 1836 года Нечаев вынужден был по семейным делам надолго отлучиться из столицы, и ведомство осталось без начальника. Тогда Андрей Муравьев при поддержке сослуживцев отважился на решительный шаг — сместить Нечаева. Он поехал к первенствующему члену Синода, Петербургскому митрополиту Серафиму (Глаголевскому), чтобы упросить его войти с докладом к Государю Николаю Павловичу о перемене обер-прокурора. Владыка согласился и, будучи на приеме у Государя, на вопрос, кем заменить предместника, назвал графа Николая Александровича Протасова, бывшего правой рукой министра народного просвещения. Впоследствии скажут, что это было сделано с подачи Муравьева, поскольку Протасов, с его гусарскими замашками, соперник несерьезный. К тому же и человек он бездуховный: посидит временно и уйдет, уступив свое место Андрею Николаевичу — "готовому обер-прокурору"5. И Протасов сел в начальствующее кресло, но не временно, а на долгие годы (1836–1855). Его обер-прокурорство отмечено разгулом формализма, увеличением штатов в Синоде, самодурством в отношениях с духовными лицами. Правда, граф Протасов исходатайствовал А. Н. Муравьеву звание камергера, поручил ему издание нового перевода Правил Вселенских и Поместных Соборов, но то частности.
В 1837 году Андрей Николаевич сопровождает Наследника престола цесаревича Александра в его паломничестве по московским святыням — от Нового Иерусалима до Троице-Сергиевой лавры. Посетили они также Кремль и близлежащие монастыри. Свои путешествия по святым местам русским — а Муравьев уже исходил и изъездил практически всю европейскую часть Отечества — он стремился описать своим чутким пером. Его книги стали доступными любому грамотному человеку; повсюду душеспасительное чтение входило в народный обиход.
Для духовных училищ Муравьев издает толкование Символа веры, а для нетвердых в вере молодых людей — "Письма о спасении мира Сыном Божиим". Перебежчиков в униатство он изобличает в двоедушии и измене отеческой традиции. С благословения митрополита Филарета Андрей Николаевич приступает к созданию церковно-исторических книг. Особое внимание в архивных разысканиях уделяет истории Русской Церкви, для этого несколько раз посещает Москву и Киев, встречается с правящими архиереями, за что получил упреки со стороны Протасова. После удаления из Синода владыки Филарета Муравьев незамедлительно подал прошение об увольнении (июнь 1842 г.). Московский святитель на этот поступок откликнулся так в письме к Муравьеву: "Ваши писательские занятия в сие время составляли деятельную и полезную службу Церкви и духовному просвещению. Утешаюсь тем, что вы приемлете происшедшую перемену со вниманием и послушанием к путям Провидения и с христианским миром чувствований".
Оставив Синод, Муравьев перешел в общее присутствие Азиатского департамента, а с 1846 года он определен чиновником особых поручений при этом же ведомстве (состоял до 1866 г.). Андрей Николаевич свободно располагал своим временем и, путешествуя, мог сочинять. Еще в 1845 году он побывал в Риме, свои размышления о поездке изложил в письмах к святителю Филарету. Когда "Римские письма" напечатали, их с пользой прочли ревнители Православия. Агенты католицизма и униаты, напротив, подняли шумную волну опровержений, выискивая и между строк антипапский оттенок. Особенно неистовствовал перебежчик в католичество князь Николай Борисович Голицын. В Париже он издал бесцветную книжку с замечаниями на "Римские письма" Муравьева, неубедительную и весьма схоластическую. Андрею Николаевичу пришлось отвечать на эти замечания, и позицию православного он защитил достойно.
С сентября 1846 до июля 1847 года А. Н. Муравьев находился в Грузии и Армении, и это свое путешествие тоже ярко описал. В 1848 году он посетил приволжские города, что нашло отображение в книге "Мысли о Православии при посещении Святыни русской". В следующем году — Афон, Иерусалим, Миры Ликийские, где некогда пребывала величайшая христианская святыня — мощи угодника Божия Николая. В Мирах Андрей Николаевич скорбел при виде руинированного монастыря всесветно чтимого святителя и решил про себя все силы приложить на его восстановление. Было положено начало сбору средств. Полвека спустя на эти и другие средства Императорское Палестинское общество построит подворье и церковь в Бари.
Муравьев писал быстро и много, его книги в огромном числе издавали и переиздавали, одно время на средства графини Анны Алексеевны Орловой-Чесменской. Дворяне, духовенство, купцы тогда были главными читателями духовной литературы. Муравьев проложил путь благочестивой книге в широкие слои русского общества, и в этом его огромная заслуга перед историей Русской Церкви. Обратил внимание Андрей Николаевич и на демонические увлечения Неверов, сурово изобличая сатанинские культы. В исторических разысканиях Андрей Николаевич обращал особое внимание на материалы, ранее неизвестные либо малоизученные. Он впервые опубликовал дело о патриархе Никоне, документы о связях Русской Церкви с Восточными Церквами, собрал множество свидетельств о православных подвижниках благочестия, издал 12 книг житий святых.
Муравьев как церковный публицист весьма созвучен своему времени. Не было ни одного существенного вопроса, поставленного духовным управлением, на который бы не последовал его ответ. А со своей мечтой стать обер-прокурором Муравьев расстался лишь в 1865 году. "Люди не допускают меня быть обер-прокурором, — печаловался он одному знакомому, — но предназначение не мимо идет — меня теперь слушают и патриархи, и митрополиты". Во многом так оно и было: к его посредничеству прибегали предстоятели славянских Православных церквей, да и отечественные иерархи не гнушались им. Что касается церковного руководства, то Муравьев стоял за соборное, патриаршее правление в России.
Давно у Андрея Николаевича созрела мысль покинуть Санкт-Петербург и поселиться в Москве. Дмитрий Николаевич Шереметев, сын Прасковьи Жемчуговой, предложил Муравьеву занять флигель в его останкинском дворце. Переезд состоялся, и Останкино произвело на писателя исключительно благоприятное впечатление. Здесь в 1853 году Муравьев приступил к написанию книги "Русская Фиваида на Севере" — пожалуй, одного из самых лучших своих творений. Работа продвигалась быстро, ведь северные обители он посещал лично, и воспоминания легко ложились на бумагу. Исторических же источников в портфеле преизобильно — собирал годами. Книга живо воссоздает быт и уклад монастырей, основанных учениками и последователями преподобного Сергия. Книга посвящена великой княгине Елене Павловне (1806–1873), жене великого князя Михаила Павловича, покровительнице муз. Замечательное сочинение Муравьева о путешествии к северным обителям, к сожалению, мало доступно даже собирателям книг, поскольку, в отличие от других его творений, не переиздавалось до 1999 года, когда издательство "Паломник" выпустило в свет этот замечательный труд, оцененный по достоинству благочестивыми читателями. Теперь издательство "Паломник" переиздает другую редкую книгу А. Н. Муравьева — "История Российской церкви". Этот труд написан доступным языком, содержание изложено четко и ясно, так что православное юношество наконец получит для чтения весьма полезное пособие.
Недолго жил в останкинском дворце Шереметевых Андрей Николаевич. Не приведи Бог обосновываться писателю в чужом доме, тем более под надзором дворецких и разной челяди, да еще с характером Муравьева и его причудами. "Выжили из Останкина, где мне было так приятно" — фраза неслучайная. В 1854 году Муравьев наведался в Киев. Здесь приобрел гористый пустырь вблизи церкви Андрея Первозванного, велел расчистить его, развести сад, для начала поставить избу. Но окончательно поменял Петербург на Киев лишь после отставки по службе в 1866 году. К тому времени в Киеве среди собственного сада уже возвышался добротный дом, построенный на занятые средства; часть расходов удалось погасить за счет пожертвований Государя. Теперь литератор не столько творил, сколько говорил: ни один любознательный путешественник к киевским святыням не обходился без сопровождения Андрея Николаевича.
В 1869 году Киев посетила Императрица Мария Александровна, в ее свите состоял и Федор Иванович Тютчев, только что вернувшийся из родового имения Овстуг. Старые приятели неделю провели в беседах, Муравьев водил поэта осматривать церковные древности седого града. Общение с другом Тютчев отобразил в дивных стихах, написанных вскоре после отъезда из Киева: