Второй сын вице-канцлера графа Андрея Ивановича Остермана (старший — Пётр — умер во младенчестве) и Марфы Стрешневой, крестник цесаревны Анны Петровны.
В 1740 году — капитан лейб-гвардии Преображенского полка, с 25 февраля 1740 года — кавалер ордена св. Александра Невского. Опала отца отразилась и на нём: 16 января 1742 года он был лишён ордена и переведён капитаном же в Троицкий пехотный полк, расположенный в Башкирских землях, где прослужил 20 лет.
Подполковник (1756). В Семилетнюю войну участвовал во всех крупных сражениях. Полковник (1758), был ранен под Кунерсдорфом. Обратил на себя внимание императрицы Екатерины и вновь занял высокое положение. С 1762 года — генерал-майор и шеф Нарвского пехотного полка, командир бригады в корпусе графа Чернышёва. Командир московской дивизии (1763).
C 1771 года — генерал-поручик; с 1773-го — московский губернатор, затем (24 ноября 1780 года) — сенатор. Действительный тайный советник (1782). Не имея детей, в 1796 году передал титул своему внучатому племяннику А. И. Толстому.
Похоронен в родовом имении, селе Красном Сапожковского уезда Рязанской губернии. Оставил интересные «Замечания на записки Манштейна о России».
Был женат на Анне Васильевне Толстой (15 февраля 1732 год, Москва — 23 мая 1809 год, Москва), дочери статского советника Василия Борисовича Толстого и его жены, Дарьи Никитишны Змеевой. 5 апреля 1797 года была награждена орденом св. Екатерины 2 степени. Похоронена в Новоспасском монастыре.
Именно в их доме в Малом Трёхсвятительском переулке (угол Хитровского переулка) жила семья Тютчевых — мать поэта, Екатерина Львовна, была племянницею Анны Васильевны). Является Объектом культурного наследия регионального значения.
15 февраля 1806 года А. В. Остерман завещает Екатерине Львовне это владение: