Такая возможность представилась в 1787 году, когда началась война с Турцией. В армии Григория Потемкина он воевал в Молдавии и Бесарабии, участвовал во взятии Бендер и Килии, сражении при Мачине, двух штурмах Измаила. В характере офицера появляются черты, которые впоследствии Алексей Ермолов объединит одним емким словом — неустрашимость.
В Петербург Толстой вернулся в 1792 году поручиком. Он был милостиво принят Екатериной II и награжден орденом святого Георгия IV степени. Но вести образ жизни гвардейского офицера не смог из-за отсутствия средств. Пришлось оставить гвардию и уехать в провинцию командовать егерским батальоном.
Толстой уже свыкся с неспешной провинциальной жизнью, когда в 1796 году его бездетные родственники графы И.А. и
В 1801 году Александр I вернул опального генерала в строй. В 1805 году Россия вступила в период войн с Францией, и Остерман-Толстой скрестил оружие с маршалами Наполеона. В декабре 1806 года, командуя арьергардом, он у Чарново с пятитысячным отрядом стал на пути корпуса маршала Даву, которого Наполеон, видя малочисленность русских, уже поздравил с победой. Но праздновать победу маршалу не пришлось. В течение десяти часов французы безуспешно атаковали русские позиции. В критические моменты боя генерал возглавлял контратаки и штыками отбрасывал противника. Только ночью он отошел к основным силам. Через несколько дней, в сражении у Пултуска, командуя левым крылом русских войск, Остерман-Толстой не только остановил наступление корпуса Ланна, прорвавшего фронт главных сил, но и перешел в наступление. И опять он был впереди атакующих колонн.
Вместе с боевыми успехами рос военный авторитет; об Остерман-Толстом сложилось мнение, как о генерале, для которого нет невыполнимых задач. Доблесть графа оценили по достоинству, он стал генерал-лейтенантом, был награжден орденом святого Георгия III степени.
Война закончилась подписанием Тильзитского мира, против которого граф открыто выступил, заявляя, что новая война с Наполеоном неизбежна и надо к ней готовиться. Его позиция была столь последовательна, что французский посланник Коленкур в донесениях называл графа «главой военной оппозиции». В 1809 году Остерман-Толстой вынужден был уйти в отставку.
В апреле 1812 года, предчувствуя приближение войны, он выехал к западной границе. В одном из первых боев с французами в рядах русских солдат появился генерал с орденом святого Георгия на шее, который, по словам командующего корпусом Витгенштейна, «принимал участие в этом деле как волонтер». Весть об опальном генерале, который в рядах солдат воюет с французами, быстро распространилась по армии. Общественное мнение было на стороне графа, и его назначили командующим 4-м корпусом.
Генерал остро переживал отступление, связывая его с засильем иностранцев в руководстве русской армии. По всей стране разошлись слова, гневно сказанные им начальнику штаба 1-й армии маркизу Паулуччи: «Для вас Россия — мундир, вы его наденете и снимете. А для меня она моя кожа».
Под Витебском он встал с корпусом на пути французов, прикрывая отступление 1-й армии. Имея значительный перевес в силах, маршал Мюрат раз за разом посылал кавалерию в атаки, но русские стояли непоколебимо. Подошедшая на помощь французам пехотная дивизия была отброшена штыками и картечью.
В Бородинском сражении генерал еще раз подтвердил репутацию неустрашимого. В критический момент боя за Курганную высоту он был переброшен на помощь Раевскому. Воодушевляемый примером командира, который сам водил полки в штыки, корпус Остерман-Толстого отбил все атаки и, поредевший почти наполовину, ни на шаг не сдвинулся с занятых позиций.
Во время преследования отступающих французов его корпус отличился при штурме Вязьмы. Затем следовал параллельно французам, не давая им свернуть со старой Смоленской дороги. В ожесточенном трехдневном бою под Красным Остерман-Толстой был ранен, но поле боя не покинул. И только после изгнания неприятеля с русской земли, граф «позволил себе» уехать лечиться. Но долго находиться вдали от армии не смог, и 8 мая 1813 года появился под Бауценом в напряженный момент сражения. Остановив отступающий гренадерский полк, повел его в контратаку. Из боя генерала вынесли потерявшим сознание от тяжелой раны в плечо.
В августе он опять вернулся в строй и отличился в сражении, которое стало кульминацией его военной карьеры. Под Кульмом, спасая отступающую союзную армию, он с 19-тысячным отрядом встал на пути 40-тысячного корпуса Вандама. Французы, зная о своем значительном превосходстве, настойчиво атаковали, но не смогли даже потеснить русских. В разгар сражения, когда граф повел войска в контратаку, ему ядром раздробило левую руку. В палатку, где врачи отнимали генералу раздробленную руку, солдаты внесли отбитое у французов знамя. Увидев его, Остерман-Толстой прошептал: «По крайней мере, я умру непобежденным». Но железная воля помогла ему снова вернуться в строй.
Несмотря на последствия тяжелого ранения, до декабря 1825 года Остерман-Толстой продолжал службу, но новому императору Николаю I нужны были послушные солдафоны, а не независимые генералы с богатым боевым опытом, и графа отправили в отставку.
В 1830 году Остерман-Толстой навсегда покинул Россию. Он прожил большую жизнь и скончался в 1857 году в Женеве. Несмотря на официальную опалу, в русской армии всегда помнили и чтили неустрашимого генерала, который ценил свободу Отечества выше собственной жизни.