В 1744 г. окончил Шляхетный сухопутный кадетский корпус. Пройдя все стадии армейского чинопроизводства, в 1773 г. получил звание генерал-поручика. Участник Семилетней, русско-турецкой 1768-1774 гг. войн.

С 1780 г. занялся управленческой деятельностью в качестве генерал-губернатора Орловского и Курского наместничеств.

В 1783 г. пожалован в генерал-аншефы с выключением из армии , а в 1784 г. последовало увольнение от службы с сохранением содержания.

После шестилетнего перерыва 19 февраля 1790 г. вернулся к административным занятиям в должности главнокомандующего в престольном городе Москве и ея губернии .

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

Более всего беспокоила А.А. Прозоровского далекая от совершенства планировка Москвы. По его настоянию началась прокладка улицы вдоль Китайгородской стены по земле Воспитательного дома (современного Китайского проезда). В 1792 г. архитектор М.Ф. Казаков осуществил планировку Тверской площади перед домом главнокомандующего. Для ее устройства Екатерина II разрешила А.А. Прозоровскому приобрести имение князей Долгоруковых против генерал-губернаторского особняка на Тверской. На площади перед резиденцией главы города по проекту М.Ф. Казакова предполагалось установить кордегардию с колоннами и железную ограду. В связи с расходами на русско-турецкую войну задуманные работы осуществить не удалось.

Но, пожалуй, самым важным вкладом А.А. Прозоровского в благоустройство столицы можно считать созданную им в 1791 г. Комиссию сочинения городу Москве плана, позднее переименованную в Комиссию о снятии плана города Москвы, деятельное участие в которой принимал зодчий М.Ф. Казаков. Московский главнокомандующий стремился выработать технически обоснованный подход к городской планировке и считал, что рассмотреть потребно переулки, которые с такими непристойными поворотами, что стыдно видеть сию связь улиц древней столицы... Несмотря на то, что подготовительные работы по обмеру дворов и подсчету их числа начались еще в 1790 г., дело двигалось довольно медленно, так как требовало тщательного и безукоснительного выполнения.

21 марта 1795 г. А.А. Прозоровский был уволен от главного начальства по прошению. В ноябре 1796 г. Павел I назначил его командиром 1-й Смоленской дивизии, но в январе следующего года уволил с должности за вступление в командование не своей части . Александр I вернул А.А. Прозоровского на службу, произвел в генерал-фельдмаршалы с назначением главнокомандующим над русскими войсками в Молдавии и в период русско-турецкой войны 1806-1812 гг. Эта запись стала последней в его формулярном списке.

Погребен в Киево-Печерской лавре. Впоследствии его прах перенесен в церковь Св. Александра Невского, что в Печерской части Киева.