С лета 1832 г. А.Н. Муравьёв совершал паломничества по России, первое (по данному им в Иерусалиме обету) в Троице-Сергиеву лавру. Затем он посетил Новоиерусалимский в честь Воскресения Христова, Иосифов Волоколамский (Волоцкий) в честь Успения Пресвятой Богородицы и Юрьев новгородский монастыри, летом 1833 г. – Спасо-Преображенский и Коневский в честь Рождества Пресвятой Богородицы монастыри, летом 1835 г. был в Ростове. На основе материалов этих поездок А.Н. Муравьёв написал серию книг «Путешествие по святым местам Русским», которые в разном составе выходили с 1836 г. Весной 1838 г. А.Н. Муравьёв впервые побывал в Воронеже. В том же году сопровождал наследника престола цесаревича Александра Николаевича в поездке по московским святыням – от Нового Иерусалима до Троице-Сергиевой лавры, затем ездил в Киев, Новгород и другие города. В 1848 г. А.Н. Муравьёв совершил путешествие по Волге. Последнее при жизни А.Н. Муравьёва, пятое издание «Путешествия…» вышло в 1863 г. в четырёх частях, в его составе собрано всё, что он писал о своих странствиях по России, а также статьи «Мысли о Православии при посещении святыни русской», «Оптина пустынь» (1851 г.), «Подвиги Соловецкой обители» (1854 г.), «Святые горы» (1856 г.), «Впечатления Украйны и Севастополя» (1858 г.). Зимой 1863/1864 гг. А.Н. Муравьёв во время Польского восстания, в подавлении которого большую роль сыграл его старший брат М.Н. Муравьёв, назначенный генерал-губернатором Северо-Западного края, совершил путешествие в Вильну; очерк «Русская Вильна» был напечатан весной 1864 г. в качестве приложения к «Путешествию по святым местам Русским». Помимо описания святынь в «Путешествии…» упоминались многие знаменитые личности, рассказывалось о беседах с ними, что оживляло повествование, например, приводилась беседа с Филаретом (Амфитеатровым) при посещении киевских пещер. Особое место среди паломнических очерков А.Н. Муравьёва занимает «Русская Фиваида на Севере» (1855 г.) – описание вологодских и белозерских пределов, посвящённое великой княгине Елене Павловне. В сентябре 1846 г. – мае 1847 г. А.Н. Муравьёв находился в Грузии и Армении, собирал материал, чтобы ознакомить соотечественников с церковной жизнью этого края. Специально для А.Н. Муравьёва были переведены ранее неизвестные на русском языке Жития грузинских святых. В Вагаршапате он остановился в покоях католикоса Нерсеса V Астракеци, с которым познакомился раньше в Санкт-Петербурге, и был представлен членам Вагаршапатского Синода. Наиболее интересные разделы сочинения А.Н. Муравьёва были переведены на греческий язык Константинопольским патриархом Констанцием I, в английском переводе вошли в «Историю Святой Восточной Церкви» Джона Мейсона Нила. На обратном пути из Грузии А.Н. Муравьёв посетил Севастополь, где случайно узнал о плане адмирала Михаила Петровича Лазарева построить Владимирский собор не в Херсонесе, где сохранились развалины древних храмов, один из которых по традиции считался местом крещения равноапостольного великого князя Владимира (Василия) Святославича, а в Севастополе; в Херсонесе же предполагалось устроить чумной госпиталь.