Служба А.Н. Муравьёва в Министерстве иностранных дел началась в августе 1828 г., с 1831 г. он служил в Азиатском департаменте и продолжал числиться в Министерстве иностранных дел после назначения в 1833 г. в духовное ведомство. Через два месяца он был уволен из духовного ведомства и 17 августа 1842 г. был определён членом общего присутствия Азиатского департамента. 7 декабря 1846 г. назначен чиновником особых поручений пятого класса при Азиатском департаменте. 17 апреля 1855 г. Высочайшим приказом по гражданскому ведомству А.Н. Муравьёва произвели в чин действительного статского советника. Приказом по Министерству иностранных дел от 28 февраля 1866 г. по случаю упразднения должности, которую А.Н. Муравьёв занимал в Азиатском департаменте, он был уволен, но ему оставили мундир, полученный в последней должности, и определили пенсию 8 тыс. руб. в год. В письме товарищу министра иностранных дел Ивану Матвеевичу Толстому (6 декабря 1860 г.) А.Н. Муравьёв отмечал, что его карьера в министерстве состояла «собственно не в бюрократических занятиях», но имела «официальную и неофициальную сторону… служения, которая не всем могла быть известна» (Отдел рукописей Российской национальной библиотеки) и была сосредоточена преимущественно на восточном направлении. С 1836 г. А.Н. Муравьёв был эпитропом Иерусалимского, затем Антиохийского и Александрийского патриарших престолов. О службе в министерстве А.Н. Муравьёв писал, что «если звание Эпитропа не даёт мне никакого официального значения по службе, то во всяком случае оно доказывает ту степень доверенности, какую, с помощию Божиею, успел я приобрести у высших сановников Востока, которые суть не только духовные, но и политические главы своего народа; а также их сближение, выходящее из обыкновенного порядка вещей, с одним из чиновников Министерства Иностранных Дел могло в своё время приносить пользу!» (Отдел рукописей Российской национальной библиотеки). А.Н. Муравьёв принимал деятельное участие в отношениях Русской православной церкви с Восточными церквами, его влияние на решение церковных вопросов проявлялось многообразно благодаря доверительным отношениям с митрополитом Филаретом (Дроздовым) и с восточными патриархами, службе при Синоде и в Министерстве иностранных дел, дружеским и родственным связям, наконец, положению А.Н. Муравьёва при дворе. Так, А.Н. Муравьёв занимался примирением насельников Синайской обители с Александрийскими патриархами, не разрешавшими синаитам иметь свою церковь в Каире (Отдел рукописей Российской национальной библиотеки), помогал в так называемом деле о камилавках. Благодаря энергичному вмешательству А.Н. Муравьёва консульство в Бейруте в 1843 г. было преобразовано в генеральное, в 1848 г. устроено Антиохийское подворье в Москве. В 1841–1842 гг. А.Н. Муравьёв содействовал учреждению православных училищ и школ в Сирии и Палестине на средства, собранные на нужды храма Гроба Господня.