Именно в это время Алексей Толстой работает над новым романом. Он давно мечтал написать что-нибудь фантастическое, сказочное. Однажды признался жене, Наталии Крандиевской-Толстой: «Знаешь, без фантастики скушно все же художнику, благоразумно как-то… Художник по природе — враль — вот в чем дело!» Действие нового романа происходит в августе 192… года в Советской России, но начинается он с объявления, написанного «обыкновенно и просто, обыкновенным чернильным карандашом»: «Инженер М. С. Лось приглашает желающих лететь с ним 18 августа на планету Марс явиться для личных переговоров от 6 до 8 вечера».
Вот так. В стране полыхает гражданская война, народ голодает, города в развалинах, а тут… Неслучайно это «объявление, приколоченное гвоздиками к облупленной стене, подействовало в высшей степени болезненно» на корреспондента американской газеты Арчибальда Скайльса.
Позже критики и литературоведы убедительно покажут, где Алексей Толстой мог позаимствовать подробности легенды об Атлантиде (теософские книги Блаватской, Штейнера, лекции Брюсова, рассказы Волошина, с которым Толстой был близок и даже выступал секундантом на дуэли Волошина с Гумилевым), что первоначальное название романа — «Закат Марса» — явилось отголоском на работу О. Шпенглера «Закат Европы», что автор был знаком и с работами К. Э. Циолковского. Все это так, но главным толчком для Толстого в работе явилась все же неизбывная тоска по России, которая отразилась и в умонастроениях героев романа. Читая готовые главы близким, Алексей Николаевич постоянно жаловался, что ему не хватает российских пейзажей, вспоминал о деревушке на Оке, где когда-то славно работал. Он часто встречался с Максимом Горьким, который в то время жил в Германии, и в голове вызревало решение вернуться на родину.
И в то же время этот роман был окончательным ответом на вопрос, который эмиграция поставила перед писателем: с кем он и что намерен делать? Ответом однозначным: писатель выбирал Россию.
В сентябре 1922 года Толстой сообщает Горькому: «Я предпринял обработку «Аэлиты» и перерабатываю ее с самого начала — ужасно много мусора. Работаю весь день…» И чуть позже: «Работаю плохо: конец «Аэлиты» — 10 страниц, — как воз, выворачиваю». А уже в октябре пишет Чуковскому: «…спешно кончаю роман («Аэлита» — «Закат Марса»). Аэлита — имя очень хорошенькой и странной женщины. Роман уже переводится на немецкий…»
Роман начал печататься в 1923 году в журнале «Красная новь» и в том же году в Госиздате вышел отдельной книгой. Позже «Аэлита» была переработана А. Толстым для детей старшего возраста и вышла впервые в Детиздате в 1937 году, а затем многократно переиздавалась.
Представляя «Аэлиту», Толстой уточнял: роман «фантастический, правда, но в нем совершенно отсутствует элемент невероятности: все, что там описано, все можно осуществить, и я уверен, что осуществится когда-нибудь… Надо Вам сказать, что я по образованию инженер-технолог, поэтому за эту сторону более или менее отвечаю».
Первая реакция на роман в России была неоднозначной. Однако Максим Горький порекомендовал «Аэлиту» для перевода иностранным издателям: «Хотя гр. А. Н. Толстой инженер по образованию, но он свел в романе технику к необходимому минимуму, и вся книга написана под влиянием увлечения догадками об Атлантиде… и вполне отвечает жажде читателя к темам не бытовым, к роману сенсационному, авантюрному. Написана «Аэлита» хорошо и, я уверен, будет иметь успех».
А вот другие литераторы приняли и роман, и возвращение Толстого, мягко говоря, прохладно.
Г. Лелевич (критик в двадцатые годы авторитетный): «Алексей Толстой, аристократический стилизатор старины, у которого графский титул не только в паспорте, дарил нас «Аэлитой», вещью слабой и неоригинальной…»
Корней Чуковский: «Роман плоховат… Все, что относится собственно к Марсу, нарисовано сбивчиво, неряшливо, хламно, любой третьестепенный Райдер Хаггард гораздо ловчее обработал бы весь этот марсианский сюжет… Куда нам, писателям технически отсталого народа, сочинять романы о машинах и полетах на другие планеты!»
Образ красноармейца Гусева Чуковский одобрил: «И все же «Аэлита» превосходная вещь, так как она служит пьедесталом для Гусева. Не замечаешь ни фабулы, ни остальных персонажей, видишь только эту монументальную, огромную фигуру, заслоняющую весь горизонт. Гусев — образ широчайших обобщений, доведенный до размеров национального типа. Если иностранец захочет понять, какие люди сделали у нас революцию, ему раньше всего нужно будет дать эту книгу. Миллионы русских рядовых деятелей революции воплотились в этом одном человеке».