Александр Иванович Толстой родился в семье Ивана Матвеевича Толстого (1746—1808) (мать которого была дочерью графа А. И. Остермана — дипломата, сподвижника Петра Великого) и Аграфены Ильиничны Бибиковой. Императрица Екатерина II дозволила молодому Толстому в 1796 году принять титул, фамилию и герб рода Остерманов от его бездетных двоюродных дедов — Фёдора и Ивана Остермана.
А. И. Толстого по обычаям с самого раннего возраста записали на военную службу в лейб-гвардии Преображенский полк. К 14-летнему возрасту он за выслугой лет числился прапорщиком. Боевую службу начал с 1788 года в войне против турок, состоял в армии князя Потемкина. Участвовал в 1790 году под командованием Суворова в штурме Измаила, награждён за отличие орденом Св. Георгия 4-го кл. С 1793 года служил в Бугском егерском корпусе, сформированном М. И. Кутузовым — мужем его тётки Екатерины Ильиничны Бибиковой.
В феврале 1798 года Остерман-Толстой, приняв к тому времени графский титул и фамилию Остерманов, произведен в генерал-майоры в возрасте 28 лет и назначен шефом Шлиссельбургского мушкетерского полка. Неожиданно для всех через 2 месяца отстраняется от военной службы в чине действительного статского советника, то есть изгоняется с военной службы. Причина немилости царя Павла I была простая, новый царь недолюбливал фаворитов своей матери, Екатерины II. Лишь после вступления на престол Александра I Остерман-Толстой смог в 1801 году вернуться в армию.
С началом войн против Наполеона в 1805 году генерал Остерман на театре боевых действий. В 1806 году произведён в генерал-лейтенанты.
27 января (8 февраля) 1807 года участвовал в сражении при Прейсиш-Эйлау. Командуя 2-ой дивизией и всем левым флангом русской армии, он сумел сдержать удар на его позиции корпуса Даву и стал по сути спасителем всей армии. Весной того же года на территории Пруссии развернулись военные действия против корпуса маршала Нея, который стремился отрезать русских от Кенигсберга. 24 мая авангард Багратиона, куда входила дивизия Остермана-Толстого, принял удар превосходящего в числе неприятеля. В этом бою Остерман был ранен в ногу пулей навылет. В октябре 1810 года Остерман, измученный раной, добился отставки с правом ношения мундира, но сразу же вернулся в строй с началом Отечественной войны 1812 года.
Во время войны он командовал 4-м пехотным корпусом в 1-й Западной армии Барклая-де-Толли, отличился под Островно и при Бородино. В Бородинском сражении Остерман-Толстой участвовал в боях на батарее Раевского, был контужен, но через несколько дней вернулся в строй.
Граф знаменит своими словами, сказанными им в бою под Островно: "Яростно гремела неприятельская артиллерия и вырывала целые ряды храбрых полков русских. Трудно было перевозить наши пушки, заряды расстрелялись, они смолкли. Спрашивают графа: «Что делать?» «Ничего, — отвечает он, — стоять и умирать!»" (C.Н. Глинка).
В кампанию 1813 года Остерман-Толстой прославил свое имя 17 августа в блестящем бою под Кульмом, где потерял левую руку, оторванную ядром. Русский художник Василий Кондратьевич Сазонов написал картину, изображающую Остермана-Толстого во время хирургической операции над ним на поле битвы под Кульмом. Ещё ранее, 9 мая 1813 года, в сражении под Бауценом он был ранен пулей в плечо.
Король Пруссии наградил Остермана Большим прусским Железным крестом, наградой, которая за всю свою историю вручалась только семь раз. Победа при Кульме закрыла наполеоновским войскам путь в Богемию, народ Чехии преподнёс герою сражения подарок. В Государственном Историческом музее хранится кубок, поднесенный «храброму Остерману от чешских женщин в память о Кульме 17 августа 1813 года», и мундир, в котором был Остерман-Толстой в момент ранения.
Остерман вернулся в Петербург в начале 1814 года и сразу же был назначен генерал-адъютантом Александра I. В этом качестве находился до самой смерти императора. В 1816 году назначен командиром Гренадерского корпуса. В августе 1817 года получает чин генерала-от-инфантерии, но его здоровье после тяжёлых ран было настолько подорвано, что он в этом же году освобождается от командования корпусом и увольняется в бессрочный отпуск, хотя продолжает числиться на военной службе.
В начале 1820-х годах Остерман-Толстой жил в Петербурге в своем доме на Английской набережной.
Во время подавления восстания декабристов в 1825 году некоторые восставшие офицеры (Д. Завалишин, Н. Бестужев и В. Кюхельбекер) укрылись в доме Остермана-Толстого, расположенном на Английской набережной. В числе декабристов оказались родственники Остермана, за которых он безуспешно хлопотал.
После вступления на престол Николая I Остерман-Толстой уехал в Италию, не поладив с новым императором.
В 1828 году граф Остерман ездил представиться императору Николаю I, чтобы предложить свои услуги на время Турецкой кампании; его предложение не было принято. Остермана окончательно уволили от службы с разрешением ехать за границу.
Остерман удалился от дел и поселился в Женеве, он приобрел и повесил в своем кабинете портрет Ермолова, служивший ему живым напоминанием славного прошлого.
Со смертью А. И. Остермана-Толстого в отсутствие его законных детей вновь мог прерваться род Остерманов. Знаменитую фамилию должен был принять племянник графа, осуждённый декабрист Валериан Михайлович Голицын, но он и его дети были восстановлены в правах только в 1856 году.
30 января (11 февраля) 1857 года года Остерман-Толстой умер в Женеве в возрасте 86 лет. В мае того же года его тело отправлено в родовое имение, село Красное Рязанской губернии Сапожковского уезда и там перезахоронено в Троицкой церкви. В 1863 году право наследования фамилии, титула и майората Остерманов «по высочайшему утверждению» получил сын В. М. Голицына — Мстислав, который стал именоваться «князь Голицын граф Остерман».
Был женат с октября 1799 года на княжне Елизавете Алексеевне Голицыной. Детей в законном браке не было.
В 1822 году Остерман-Толстой поселил у себя (на Английской набережной в СПб, теперь д. 10) своего дальнего родственника, известного русского поэта Фёдора Тютчева, семья которого давно дружила с Остерманами. Есть свидетельства, что именно Тютчев познакомил за границей Остермана-Толстого с некой итальянкой из Пизы, от которой граф имел детей. По воспоминаниям адъютанта И. И. Лажечникова, произошло это после смерти Елизаветы Алексеевны. Остерман выдал итальянку с богатым приданым за её соотечественника, детям дал хорошее воспитание и обеспечил. В наше время в Швейцарии до сих пор живут потомки полководца. Они чтут память своего знаменитого предка, берегут его личные вещи, боевые награды, интересуются русской историей, самостоятельно изучают русский язык и приезжают в гости в Россию.