Сын генерал-майора Николая Муравьева, Андрей Муравьев родился в Москве. Мать умерла, когда ему было 3 года, и мальчика вверили попечению петербургских родственников. В 1815 году девятилетний Андрей Муравьев вернулся в Москву, где его отец возглавлял «школу колонновожатых», готовившую штабных офицеров. «14-ти лет, — вспоминал впоследствии Андрей Николаевич, — я имел наставником доброго и почтенного Раича… Он совершенно образовал меня и кончил мое домашнее воспитание. Он вселил в меня всю склонность к литературе».
В 1823 году Муравьев был зачислен юнкером в егерский полк, спустя полгода перевелся в драгунский полк и получил чин прапорщика. Он служит на Украине, в Молдавии, в августе 1825 года едет в Крым, где знакомится с Грибоедовым и беседует с ним на литературные темы. Пребывание в Крыму развивает в нем страсть к поэзии, которую с тех пор Муравьев избирает своей целью.
Взяв отпуск, в 1826 году Муравьев приезжает в Москву и довольно быстро становится известным в литературных кругах. Он посещает салон З. А. Волконской, встречается с Пушкиным, Вяземским, Боратынским, печатается в альманахе Раича «Северная лира», издает сборник своих стихотворений под заглавием «Таврида», который публика, впрочем, встретила довольно прохладно. Муравьев погружается в изучение творений Данте и Торквато Тассо. Его вообще пленяет масштабность в творчестве, и замыслы его грандиозны. Он хочет окончить «Потерянный рай» Мильтона и «Мессиаду» Клопштока монументальной поэмой собственного сочинения «Потоп», задумывает написать целый ряд трагедий на сюжеты из русской истории, усердно трудится над трагедией «Битва при Тивериаде», изображающей падение Иерусалима и изгнание крестоносцев из Палестины.
Муравьеву и самому довелось увидеть «святые места». В 1829 году он отправляется в Палестину и Египет. Итогом полугодового странствия явилась книга «Путешествие ко святым местам в 1830 году», имевшая значительный успех, в отличие от трагедии «Битва при Тивериаде», постановка которой на сцене Александринского театра закончилась полным провалом.
Муравьев оставляет поэзию и обращается к религиозной публицистике и истории православной церкви. Он служит в Святейшем синоде и в Азиатском департаменте, уверенно повышаясь в чинах. Общество, впрочем, не слишком жаловало Муравьева, называя его фискалом, ханжой, Андреем Незваным и светским архиереем. Андрей Николаевич, предавшись духовному направлению, отнюдь не чуждался рассеянной, мирской жизни. В великосветских гостиных он обыкновенно появлялся в черном жилете, с четками в левой руке, изумляя собравшихся своим колоссальным ростом.