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