19 января 1772 г. (указанный во многих источниках 1770-й – ошибочная дата) в Петербурге в семье дворянина Ивана Матвеевича Толстого родился сын Александр. С раннего возраста, по обычаю тех лет, он был записан на военную службу в лейб-гвардии Преображенский полк и к 14 годам уже имел чин прапорщика. Боевое крещение юного офицера пришлось на 1788 г., когда Остерман впервые отличился в русско-турецкой кампании. Храбрость при штурме Измаила в 1790-м принесла ему первый крест – почетнейший орден Святого Георгия 4-й степени.

27 октября 1796 г. полковник Толстой стал графом Остерманом-Толстым. Дело в том, что Александр доводился внучатым племянником последним представителям графского рода Остерманов, и, чтобы славная фамилия не угасла, ее вместе с титулом и гербом передали Толстому. В феврале 1798 г. 26-летний граф был произведен в генерал-майоры с назначением состоять шефом Шлиссельбургского мушкетерского полка. Но вскоре последовала опала со стороны Павла I, выразившаяся в том, что генерала переименовали в гражданский чин действительного статского советника. Вернуться в армию Остерман-Толстой смог только после воцарения Александра I, в 1801 г. – новый император питал к молодому генералу самые добрые чувства. Впрочем, их граф вызывал практически у всех знавших его людей. Его адъютант И.И. Лажечников так вспоминал об Остермане-Толстом: «Мелочным интриганом никогда не был, кривыми путями не ходил и не любил тех, кто по ним ходит; никогда не выставлял своих заслуг и ничего не домогался для себя, лести терпеть не мог. Для стрел, откуда бы ни шли, смело выставлял грудь свою. О пище и здоровье солдат заботился, как отец. Когда стояли войска в лагере, он почти каждый день обходил их во время трапезы, всегда пробовал солдатскую пищу, и горе начальнику, у которого в полку находил ее скудною или нездоровою!.. Против суровостей русских непогод граф, казалось, закалил себя; нередко в одном мундире, в сильные морозы, делал смотр полкам. Это была железная натура и телом, и душою».

Эпоха Наполеоновских войн раскрыла военный талант Александра Ивановича как нельзя более полно. В январе 1807 г., участвуя в сражении при Прейсиш-Эйлау, командир 2-й пехотной дивизии генерал-лейтенант граф Остерман-Толстой не дрогнул под напором атаковавшего его части французского корпуса Даву и дал тем самым возможность русской армии отразить натиск. За мужество, проявленное на поле боя при Пултуске, Остерман-Толстой был награжден орденом Святого Георгия 3-й степени, став 137-м по счету кавалером этой награды. Всего же по итогам кампании он получил три высоких русских ордена – Святого Владимира 2-й и 1-й степеней и Святой Анны 1-й степени, Золотую шпагу с надписью «За храбрость» и прусский орден Черного Орла.

24 мая 1807 г. генерал был ранен пулей в ногу. Рана оказалась настолько серьезной, что граф вышел в отставку с правом ношения мундира, но с началом Отечественной войны 1812 г. сразу же вернулся в строй. Легендарной стала фраза Остермана-Толстого, произнесенная тогда и адресованная одному из немецких по происхождению генералов русской армии: «Для вас Россия – мундир, вы его надели и снимете, когда захотите. Для меня Россия – моя кожа».

В 1812 г. 4-й корпус под командованием Остермана-Толстого отличился в тяжелейших сражениях при Островно (там граф отдал своим солдатам лаконичный приказ «Стоять и умирать») и Бородино. М.И. Кутузов так характеризовал действия своего подчиненного на Бородинском поле: «Примером своим ободрял подчиненные ему войска так, что ни жестокий перекрестный огонь неприятельской артиллерии, ни нападения неприятельской конницы не могли их поколебать, и удержали место свое до окончания сражения». За Бородино граф Александр Иванович был удостоен ордена Святого Александра Невского.