Муравьев с детства получил религиозное воспитание и хорошее домашнее образование, что было традиционно для московского высшего общества того времени. Говоря о традиционности воспитания Муравьева, мы имеем в виду особый тип и особый колорит московской жизни и мысли. Даже если выходцы из старомосковских, традиционного уклада, семейств жили потом в Петербурге, они культурными корнями своими восходили к московскому духовному архетипу тогда как в целом русское общество того времени отнюдь не отличалось большим интересом к православной духовности. Отметим один выразительный штрих: во всех сочинениях, письмах, документах Пушкина ни разу не упоминается день ангела, как будто эта тема для Александра Сергеевича не существует. Мы не знаем, в честь какого святого Александра поэт был назван. А для Муравьева праздник апостола Андрея Первозванного – это главный в году день: вся жизнь Андрея Николаевича строится вокруг его ангела. Он стал ктитором Андреевского скита на Афоне, поселился в Киеве возле Андреевского собора, в крипте которого и был похоронен. В этом, церковно-бытовом, смысле Муравьев с юных лет явно выделялся из своего светского и литературного окружения.
Главная роль в образовании Муравьева принадлежала С. Е. Раичу (1792–1855), поэту, переводчику, филологу, воспитателю и наставнику А. В. Шереметева, Ф. И. Тютчева и позже М. Ю. Лермонтова. Кстати, Раич приходился родным братом митрополиту Киевскому Филарету (Амфитеатрову). В творческой атмосфере литературных вечеров, где Раич читал свои переводы из поэмы Торквато Тассо «Освобожденный Иерусалим», интерес Андрея Николаевича к эпохе крестовых походов получил мощный импульс. «Тогда уже, – вспоминал Н. В. Путята, – он мечтал о путешествии на Восток, который сильно занимал его воображение как колыбель христианства и поприще крестовых походов».
Свою карьеру Муравьев начинал «архивным юношей», хотя пребывание его в Московском архиве Коллегии иностранных дел (1822–1823) было непродолжительным. По стопам старших братьев он решает определиться в военную службу, получив в декабре 1823 г. чин прапорщика. Как пишет современный исследователь, «представление о военной службе у Муравьева было, по-видимому, связано с очень важной для него идеей – идеей рыцарства… Но по своему складу он не был военным человеком и, вполне сознавая это, относился к службе как к промежуточному, временному этапу своей жизни».