В своих служебных обязанностях А. Н. Муравьев ревностно отстаивал интересы Церкви, подчас вступая в конфликты с «оком государевым». Так, при его участии был смещен Николаем I обер-прокурор С. Д. Нечаев, открыто ущемлявший права архиереев в Святейшем Синоде. Но на освободившийся пост император назначил не Муравьева, по мнению многих, наиболее подготовленного кандидата, а графа Н. А. Протасова, который еще более усилил централизованный контроль государства над церковной жизнью.

Известно было, что Муравьев сам претендовал на пост обер-прокурора, но не только из честолюбия, а из желания уничтожить эту должность и вернуть Русскую Церковь к каноническому патриаршему управлению. Будущим Патриархом он, как и многие в России, видел митрополита Московского.

Впрочем, своими пламенными порывами он нередко заставлял святителя Филарета роптать: «Вчерашний вечер подал мне случай к утешительному размышлению, что враги меньше могут вредить человеку, нежели друзья, – с немалой иронией писал он Муравьеву 15 марта 1837 года, после их долгого разговора во время болезни митрополита. – Найдет ли враг случай, изобретет ли план задушить человека долгим разговором во время болезни горла? А для друга это возможно».

Сам же святитель Филарет частенько удерживал не в меру горячего и порывистого Муравьева от скоропалительных решений и терпел его упреки, замечания, понукания, снисходительно переводя это в шутку, ибо высоко ценил искренность его служения делу Церкви.

Так, в письме от 12 августа 1835 года митрополит Филарет, в частности, пишет А. Н. Муравьеву: «Относительно ректора академии Поликарпа вы обвиняете меня в послаблении, а другие почитают меня гонителем его. Укажите мне дорогу между сими крайностями – я тотчас пойду по ней, но и тут надобно прибавить: если позволят».

Из воспоминаний современников известно, что требование Муравьева об удалении архимандрита Поликарпа (Гайтанникова) было порождено следующим случаем. В один из своих приездов в Троицкую Лавру Муравьев гулял по окрестностям и увидел ректора Духовной Академии с несколькими профессорами на берегу пруда с удочками в руках. Завязался шутливый разговор, в котором Муравьев невпопад сказал какой-то текст, приписав его апостолу. «А какой апостол это сказал?» – с улыбкой спросил ученый монах. «Апостол Муравьев так говорит!» – с досадою ответил Андрей Николаевич. «А таких апостолов недавно вешали», – со смехом возразил архимандрит Поликарп, намекая на казнь декабриста Сергея Муравьева-Апостола. Муравьев был взбешен этой шуткою и добился-таки своего: архимандрита Поликарпа сняли с поста ректора.

Масштабы деятельности А. Н. Муравьева в Святейшем Синоде выходили за рамки границ России. Его путешествия на Восток сблизили его с главами православных Поместных Церквей, которые нашли в нем постоянного и усердного ходатая обо всех нуждах бедствующих под турецким игом единоверцев. Муравьева почтили титулом епитропа (попечителя) патриарших престолов. Благодаря его хлопотам и усилиям в Москве были устроены Антиохийское, Александрийское и Иерусалимское подворья; на Афоне был создан новый русский скит во имя святого Андрея Первозванного, ктитором которого стал Муравьев. Он организовал сбор подаяний для восстановления из развалин великолепной базилики в Мирах Ликийских, где ныне покоятся мощи святителя и чудотворца Николая.

В самой России Путешественник стал восприниматься как главный эксперт по всем вопросам Христианских Церквей на Востоке, и в его консультациях нуждались и Синод, и МИД, и Зимний дворец. Вероятно, что именно Муравьев дал представление митрополиту Филарету о ближневосточных церковных проблемах, и его советами пользовался святитель при решении некоторых конкретных вопросов. Например, в декабре 1859 года митрополит рекомендует обер-прокурору Святейшего Синода графу А. П. Толстому перевести архимандрита Антонина (Капустина) на должность настоятеля посольской церкви в Константинополе; тогда же он посоветовал Синоду оставить попытки вмешательства в дела Константинопольской