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