Свою карьеру Муравьев начинал «архивным юношей», хотя пребывание его в Московском архиве Коллегии иностранных дел (1822–1823) было непродолжительным. По стопам старших братьев он решает определиться в военную службу, получив в декабре 1823 г. чин прапорщика. Как пишет современный исследователь, «представление о военной службе у Муравьева было, по-видимому, связано с очень важной для него идеей – идеей рыцарства… Но по своему складу он не был военным человеком и, вполне сознавая это, относился к службе как к промежуточному, временному этапу своей жизни».
Время военной службы (1823–1829) стало для молодого Муравьева и временем расцвета поэтического творчества, тесного общения с литературными кругами Москвы, признания его как многообещающего поэта. «Это время становления и личностного, и творческого, – пишет Н. А. Хохлова, – когда Муравьев находит свое предназначение в поэзии и начинает много и неустанно работать». В 1827 г. издан сборник стихов «Таврида», в списках ходили его трагедии «Митридат» (1825) и «Владимир» (1826). К концу 1827 г. завершена работа над трагедией «Битва при Тивериаде, или Падение крестоносцев в Палестине» (автор решится напечатать ее лишь в последний год жизни – в 1874 г.). Знаменательно, что интерес к Иерусалиму возник у него задолго до первой поездки на Восток.
К этому времени относятся воспоминания одного из друзей-сослуживцев, просто и сердечно запечатлевших образ Андрея Николаевича времен его воинской службы: «Муравьев был годами тремя старше меня, мне же перед тем минуло восемнадцать лет. Мы скоро подружились. Муравьев был исполинского роста и приятной наружности. При всей набожности своей он был нрава веселого, сердца доброго, обходителен и любим всеми товарищами, хотя постоянно удалялся от веселых компаний. Он в жизни был весьма воздержан, не пил ни капли никакого вина, любил порядок, чистоту, лошадей и верховую езду. Он тогда уже усердно занимался литературой, и первые произведения его пера сохранились у меня в альбоме и на отдельных листах».
В 1827 г. не удовлетворенный полковой жизнью и явно отдававший предпочтение карьере литературной, Муравьев подает в отставку. Но началась Русско-турецкая война 1828–1829 гг. – и он немедленно, несмотря на упреки в непостоянстве, просится обратно, причем непосредственно к театру военных действий. «Меня радовала война, – вспоминал впоследствии Муравьев, – я был напитан духом крестоносцев, которых недавно описал; мое пылкое воображение заранее представляло мне Царьград, волшебные края Греции и самый Иерусалим, всегдашнюю цель моих странствий. Меня одушевляла мысль о свержении ига неверных с единоверцев, и, когда других занимали собственные виды, я видел пред собою один лишь подвиг веры!»
10 августа 1828 г. А. Н. Муравьев был «по Высочайшему указу определен в ведомство Коллегии иностранных дел, с причислением его к Дипломатической Канцелярии Господина Главнокомандовавшего 2-ю Армиею Генерал Фельдмаршала Графа Витгенштейна». Находясь при Главной квартире главнокомандующего Дибича, он был очевидцем заключительных событий войны и подписания Адрианопольского мира (14 сентября 1829 г.). Но с окончанием военных действий он не спешит домой. Совсем наоборот. Получив через главнокомандующего русской армии И. И. Дибича-Забалканского высочайшее разрешение, Муравьев отправляется – через Константинополь, Египет, Сирию – в первое свое путешествие в Святую Землю.
Он прибыл в Иерусалим «в пятое воскресенье Великого поста», т. е. 23 марта 1830 г., и Пасху встретил в храме Гроба Господня. Это была его весна – не только в календарном, но и в духовном и творческом смысле.
Мы вернемся еще к иерусалимским сюжетам, но сначала несколько слов о дальнейшем, не очень длинном «послужном списке» писателя. Результатом путешествия была книга, ставшая поистине судьбоносной в его жизни. В апреле 1833 г., по прочтении «Путешествия» императором Николаем I, Муравьев назначается на службу в Св. Синод, секретарем обер-прокурорского стола, «с оставлением его причисленным к ведомству МИД». Несколько лет спустя он стал центральной фигурой в бюрократической интриге, связанной со смещением обер-прокурора С. Д. Нечаева и назначением на его место графа Н. А. Протасова. Существуют мемуарные свидетельства, что Андрею Николаевичу самому хотелось стать обер-прокурором, и, похоже, такая цель ставилась не им одним, но и его высокими покровителями, включая митрополита Московского Филарета (Дроздова).
Затея не удалась, кончилось тем, что сначала Филарета перестали приглашать в Синод («шпоры графа Протасова цеплялись за мою мантию», с грустной иронией скажет впоследствии святитель), а за ним ушел (в 1842 г.) и Муравьев. Местом его службы остается Министерство иностранных дел (до 1866 г.).