Отец часто вспоминал об участии в Семилетней войне и войне с Турцией 1768–1774 годов, он любил рассказывать домочадцам про свои «подвиги, лишения и страдания в ту пору, когда едва не выпало ему на долю умереть с голоду в молдавских степях». И, конечно же, Александр хотел стать военным. Препятствий его желанию не предвиделось, тем более что задолго до того, как он стал мечтать о военной службе, отец по традиции того времени записал своего четырехлетнего сына в лейб-гвардии Преображенский полк. С 1774 года полковой писарь аккуратно делал соответствующие записи в формулярном списке Александра Толстого: «Определен в службу 1774 года января 1; сержантом 1780 года января 1; прапорщиком 1784 года января 1…» Четырнадцати лет от роду Александр Иванович Толстой явился в полк, и для будущего знаменитого генерала началась действительная военная служба.

Такое ее начало было обычным явлением для молодых людей, происходивших из дворянских семей, имевших влияние и связи в Петербурге. Родители записывали своих детей в гвардию, зная, что обеспечивают им не только стремительную военную, но и придворную карьеру. Зачисление в Преображенский полк было особенно почетным, так как это был один из старейших полков — родоначальников гвардии, образованных Петром I и участвовавших в войнах той эпохи. Но после смерти Петра I гвардейские полки редко участвовали в боях и походах, в основном принимая участие в дворцовых церемониях, празднествах, увеселениях, несли караульную службу в царских покоях. Служба в столичном гарнизоне, требовавшая к тому же значительных денежных расходов, мало соответствовала описаниям походной жизни, с детства увлекавшим воображение Толстого. Где много роскоши, считал он, там мало доблести. Юный преображенец карьере царедворца предпочитал военные опасности…

12 августа 1787 года Турция, надеясь взять реванш за прежние поражения, объявила России войну, а спустя два месяца Петербург с ликованием воспринял известие о блестящей победе русского оружия. 1 октября войска Суворова, входившие в состав Екатеринославской армии Г. А. Потемкина, наголову разгромили турецкий десант на Кинбурнской косе.

В это время Екатерина II, желая возродить былую славу гвардейских полков, приказала сформировать из гвардейских войск батальон волонтеров (добровольцев) для отправки в Екатеринославскую армию. Прапорщик Толстой подал прошение о зачислении его в этот отряд.

Впервые в боевых действиях юный Толстой, будучи уже подпоручиком, участвовал 7 сентября 1789 года на реке Сальче, где армия Н. В. Репнина, поразив неприятеля, преследовала его до города Измаила; 4 ноября он находился при взятии города Бендеры, где, окруженный русскими войсками, без боя сложил оружие 16-тысячный турецкий гарнизон. Это были первые шаги будущего военачальника на военном поприще. Но своим истинным боевым крещением он считал штурм крепости Измаил, который запомнился ему на всю жизнь.

Осенью 1790 года русское командование стягивало силы к Измаилу, к этой самой могучей твердыне турецкого владычества в Причерноморье. Гарнизон Измаила без труда отразил разрозненные атаки русских войск, и они вынуждены были перейти к осаде, изнурительной не столько для осажденных, как для осаждавших, среди которых находился и подпоручик Александр Толстой.

Осень стояла в тех краях сырая и дождливая. Укрываться от непогоды приходилось в ветхих палатках, износившаяся одежда согревала плохо. Подводы с продовольствием вязли в непроходимой грязи на дорогах. Из-за голода и холода в армии распространились болезни, уносившие ежедневно сотни людей. А вокруг на десятки верст расстилалась бесприютная серая степь, порывистый ветер рвал облака, несущиеся по небу. «Кроме степи, неба и неприятеля, нигде ничего не видно», — горько шутили офицеры. И подпоручик Толстой каждый день невольно смотрел в ту сторону, где сквозь осенний туман прорисовывались грозные валы Измаила.

О силе этой крепости он знал не понаслышке. Еще 12 октября 1789 года он участвовал в неудачной для русских атаке Измаила, находясь в войсках Н. В. Репнина. А в ноябре 1790 года неутомимый подпоручик-волонтер уже служил на Черноморской гребной флотилии генерал-майора Иосифа де Рибаса, которая, пустившись по Дунаю, очистила его от турецких лодок. Войска де Рибаса овладели крепостями Тульчей, Исакчей и Килией. При взятии последней в числе отличившихся был и Толстой. 18 ноября гребная флотилия, войдя в Килийский рукав Дуная, появилась у самых стен Измаила. 20 ноября Толстой принимал участие в жестоком бою, во время которого была уничтожена турецкая флотилия, прикрывавшая крепость с юга… Измаил стоял непоколебленный. Осада продолжалась. И подпоручик Толстой вместе со всеми в армии столько же мало верил в ее успех, сколько и в возможность удачного штурма. Как вдруг 2 декабря в русский лагерь прибыл для принятия командования А. В. Суворов. Толстой видел, как разом оживились русские воины. «Быть штурму!» — говорила они друг другу с уверенностью. Юный офицер слышал, как его начальник генерал де Рибас, встретившись с полководцем, громко произнес: «Вы один, дорогой герой, стоите 100 тысяч человек!» И он сам, Александр Толстой, никогда прежде не служивший в войсках Суворова, воспрянул духом вместе с его старыми соратниками. Хотя чин подпоручика он получил не за участие в парадах и навыки поведения в бою пришли к нему не на маневрах, но опыт, боевой и нравственный, приобретенный именно под Измаилом, остался с ним на всю жизнь.

Решившись на штурм крепости, старый полководец активно готовил к нему войска. Толстой видел, как Суворов лично выезжал с офицерами к самым стенам Измаила, чтобы каждый из них заранее изучил тот участок, где ему придется вести вверенные ему войска на приступ грозной твердыни. По приказу состарившегося в битвах военачальника, солдаты выстроили подобие измаильского вала со рвом, и Суворов лично учил их, как засыпать ров фашинами, ставить штурмовые лестницы, взбираться на вал и колоть штыком. У него хватало времени и сил следить за тем, как одеты и накормлены воины. По его распоряжению из-под Галаца были вызваны маркитанты с продовольствием. В военном деле для Суворова не было мелочей. Все старался предусмотреть полководец, сознававший, что ему вверены жизни тысяч людей, которые должны были вскоре по его приказу победить или умереть. С появлением Суворова в русском лагере в войсках появилась уверенность в победе. Эту уверенность испытывал и юный Толстой, проникаясь ею от своих более опытных соратников.

Вечерами после учений он часто навещал генерал-майора Михаила Илларионовича Голенищева-Кутузова, командира Бугского егерского корпуса. Михаил Илларионович был женат на сводной сестре матери Толстого, Екатерине Ильиничне Бибиковой, и всегда радушно принимал своего юного родственника, сменившего, как и он в свое время, привольную жизнь в Петербурге на военные лишения. Толстой всякий раз с невольным любопытством смотрел на генерала, за которым в то время уже прочно укоренилась слава опытного и мужественного военачальника, испытанного в боях с турками. Офицеры, с которыми подпоручик свел знакомство в лагере, передали ему отзыв Суворова о Кутузове: «Умен, умен; хитер, хитер, его и Рибас не обманет». В армии много говорили о необычных ранениях генерала. В турецких войнах неприятельская пуля настигала его дважды. В 1788 году до Толстого дошел слух, что Кутузов получил под Очаковом рану, всем казавшуюся тогда смертельной: пуля прошла сквозь голову почти в том же самом месте, где и пять лет назад в бою под Алуштой. Но вместо известия о смерти родственника Толстой вскоре узнал, что тот, оправившись от ранения, продолжает службу. И вот теперь под Измаилом подпоручик видел его живого и здорового, и лишь когда Михаил Илларионович поворачивался к собеседнику правой стороной лица, то сразу же становилось видно, как жестоко иссечено оно шрамами, а правый глаз, казалось, смотрел более тускло. Вообще же в облике военачальника, которого так отличал Суворов, Толстой находил мало воинственного: полная, приземистая фигура, мягкий и проницательный взгляд темных глаз, доброжелательность и приветливость в обхождении, неспешность в движениях — все это само собой сразу же наводило на мысль, что круг интересов Кутузова не замыкался на воинской службе. Он действительно был очень образован, чрезвычайно начитан, любознателен, изучил иностранные языки, путешествовал по Европе, слыл знатоком всех тонкостей придворного этикета, что не мешало ему находить общий язык с солдатами и быть любимым ими. Кроме того, М. И. Кутузов был превосходным рассказчиком, и Толстой мог часами слушать своего родственника, считая, что беседа с ним является не только приятным, но и полезным, поучительным времяпрепровождением. Однажды, когда разговор зашел о воинской службе, Кутузов произнес слова, которые врезались в память. «Знаешь ли ты, мой друг, что такое солдат? Ты еще молод. Я же получил чины, и ленты, и раны; но лучшею наградою почитаю то, когда обо мне говорят: он настоящий русский солдат».