Так или иначе, разрыв между супругами Толстыми произошёл, и шестинедельного Алексея Толстого мать перевозит на Черниговщину, в своё имение Блистава, а затем в Красный Рог Мглинского уезда – имение брата, А.А. Перовского.
Первые стихотворные опыты Толстого относятся к 1823–1824 годам, а зимой 1826 года А.А. Перовская с сыном и братом возвращаются в Петербург. Здесь происходит знакомство Алексея с наследником престола, будущим императором Александром II (он на полгода младше Толстого). В том же году становится «товарищем для игр» наследника. Осенью Алексей Перовский встречается в Москве с Пушкиным. Вероятно, с ним был и племянник.
Летом 1827 года, путешествуя по Германии, Перовский, мать Толстого и он сам знакомятся в Веймаре с Гёте. Существует свидетельство, что автор «Фауста» тепло встретил будущего поэта и подарил мальчику обломок бивня мамонта с собственным рисунком фрегата на нём.
Особая часть жизни Толстого – его дружба с наследником престола. Интересная история произошла 30 августа 1829 года, в день ангела Александра. Дед по матери, король прусский Фридрих-Вильгельм III, прислал внуку оловянных солдатиков. Дети – наследник и Толстой – разыгрались. Вошедший в комнату император Николай I увлёкся игрой и в конце концов присоединился к детям.
В 1831 году, отправившись с матерью и дядей в Италию, Толстой ведёт дневник. В Риме знакомится с К.П. Брюлловым, который делает рисунок в альбоме Толстого.
Государственную службу Толстой начал в 1834 году. Он зачислен «студентом» в Московский Главный архив Министерства иностранных дел, в котором в разное время служили многие известные деятели русской культуры – братья Веневитиновы и Киреевские, С.П. Шевырев, А.И. Кошелев… Он продолжает писать стихи, о них одобрительно отзывается В.А. Жуковский. Предполагают, что творческие опыты юного поэта поддержал и Пушкин. В начале декабря 1835 года Толстой подаёт прошение в Московский университет о допущении к сдаче университетского экзамена – «из предметов, составляющих курс словесного факультета, для получения учёного аттестата на право чиновников первого разряда», а 4 января 1936 года Совет Московского университета выдаёт Толстому аттестат на вступление в первый разряд чиновников государственной службы.
В это же время Толстой влюбился в княжну Елену Мещерскую, но обстоятельства жизни не способствовали развитию этого чувства: против выступает мать, а в июне он уезжает в Ниццу, сопровождая А.А. Перовского, больного «грудной болезнью» (очевидно, туберкулёзом). Но поездка обрывается в Варшаве: здесь 9 июля Алексей Алексеевич умирает на руках племянника… Толстой наследует всё состояние дяди, в том числе имение Погорельцы в Новозыбковском уезде Черниговской губернии.
25 ноября 1837 года после хлопот Толстого и его матери он переводится в Петербург в Департамент хозяйственных и счётных дел. Представлен к чину коллежского регистратора.
Вскоре Толстой назначен «к миссии нашей во Франкфурте-на-Майне, сверх штата». Он живёт в Германии, Италии, Франции. Пишет первые рассказы (на французском языке) – «Семья вурдалака», «Встреча через триста лет». Идёт служебный рост. В октябре 1839 года произведен в губернские секретари, 9 марта 1840 года пожалован в коллежские секретари, а в декабре того же года по Высочайшему повелению перемещён «младшим чиновником» во Второе Отделение Собственной Его Императорского Величества канцелярии.
В следующем году состоялся литературный дебют Толстого-прозаика: 15 мая 1841 года цензура дала разрешение на издание книги «Упырь. Сочинение Краснорогского» (СПб); псевдоним – от имения Толстого «Красный Рог».
26 января 1842 года Толстой пожалован в титулярные советники. В «Журнале Коннозаводства и Охоты» (№5) он публикует очерк «Два дня в Киргизской степи». Служебный и творческий рост Толстого в те годы шли наперегонки. Вообще в 1840-е годы он ведёт жизнь, обычную для светского человека той поры: частые отпуска со службы, путешествия, балы, охота, мимолётные романы… Современник описывает его как «красивого молодого человека, с белокурыми волосами и румянцем во всю щёку». Толстой славится своей силой: «свёртывал в трубку столовые ложки и вилки, вгонял пальцем в стену гвозди и разгибал подковы».
В мае 1843 года Толстой – камер-юнкер, а осенью он дебютирует как поэт – в «Листке для светских людей» (№40) без подписи опубликовано его стихотворение «Серебрянка» («Бор сосновый в стране одинокой стоит…»).
В 1845 году Толстой пожалован в коллежские ассесоры. В литературном сборнике графа В.А. Соллогуба «Вчера и сегодня» публикует рассказ «Артемий Семенович Бервенковский».
1846 год, январь: Толстой – надворный советник. Во второй книге сборника «Вчера и сегодня» появляется «Амена» – фрагмент из романа Толстого «Стебеловский». Правда, больше ничего об этом произведении не известно.