В 1823–1835 годах Андрей Муравьев ощущает себя поэтом, пишет стихи, поэмы, стихотворные драмы. В первом поэтическом сборнике «Таврида» проявилось романтическое увлечение автора природой и русской историей. Позднее он пишет драму «Битва при Тивериаде, или Падение крестоносцев в Палестине», задумывает грандиозную поэму «Потоп» – и в этом видны как влияние Раича, так и пробудившийся интерес к церковным и библейским сюжетам. В 1820-е годы русское дворянское общество переживало период увлечения разными мистическими учениями, начался перевод Библии на современный русский язык (оборванный в 1824 году на три с лишним десятилетия), библейские темы притягивают поэтов – все это сыграло свою роль в определении круга интересов молодого человека.
По своему рождению и по талантам Андрей Муравьев сразу оказался среди блестящей аристократической молодежи. Впрочем, известный своим злоязычием князь П. В. Долгоруков, будущий эмигрант, признавая достоинства Муравьева, называл его «известным интриганом», склонным вмешиваться в чужие дела и заслужившим прозвище Андрей Незванный.
О стихах молодого красавца Муравьева с одобрением отзываются А. С. Пушкин и П. А. Вяземский, он входит в московский кружок «любомудров», принят в салоне княгини Зинаиды Волконской. Но случались у него и досадные неудачи. В один из весенних дней 1827 года высокий и плечистый Муравьев в салоне Волконской случайно задел и повредил статую Апполона. Свою промашку он по-светски обернул в шутку, тут же написал экспромт: «О Аполлон! Поклонник твой хотел помериться с тобой…». Однако, когда случай стал известным, Пушкин написал язвительную эпиграмму: «Ты, соперник Апполона, Бельведерский Митрофан». Оскорбительными были и тон, и намек на отсутствие формального образования. Имя героя фонвизинской комедии воспринималось как синоним глупца. Причина дерзости в этом кругу была известна: поэт страшился предсказанной ему гадалкой гибели от руки «высокого белокурого красавца» и решил испытать судьбу, ведь эпиграмма была явным поводом к дуэли. К счастью, дело обошлось без поединка.
В то время принято было молодым дворянам служить в армии. Андрей Муравьев после некоторых колебаний поступил на военную службу в 1823 году, начав ее юнкером 34-го егерского полка Второй армии, расквартированной на Украине. По дороге к месту назначения семнадцатилетний юноша едва не утонул при переправе через разлившийся Днепр. В этом испытании и в чудесном спасении он увидел явный промысел Божий. Киево-Печерская Лавра со всеми ее святынями и сам дивный Киев, раскинувшийся на зеленых холмах над широкой рекой, произвели такое сильное впечатление на Муравьева, что он решил при первой возможности навсегда поселиться здесь – и в конце жизни смог выполнить свое решение. В те годы, по воспоминаниям современника, Муравьев «был исполинского роста и приятной наружности. При всей набожности своей он был нрава веселого, сердца доброго, обходителен и любим всеми товарищами, хотя постоянно удалялся от веселых компаний. Он в жизни был весьма воздержан, не пил ни капли никакого вина, любил порядок, чистоту, лошадей и верховую езду. Он тогда уже усердно занимался литературой…».