На военной службе А. А. Беклешов находился до 1783 года и достиг чина генерал-майора. Затем Екатерина II назначила его губернатором в Риге, где за шесть лет он сумел провести немало полезных мероприятий и завоевать любовь местного населения. В 1789 году Александр Андреевич получил чин генерал-поручика и новое, более высокое назначение — генерал-губернатора Орловского и Курского наместничества. Здесь он служил шесть лет, получив за труды орден Св. Александра Невского.
Вступивший на престол Павел I беспрестанно переводил А. А. Беклешова с одной должности на другую. За непродолжительное время он был каменец-подольским и малороссийским генерал-губернатором, киевским военным губернатором и одновременно шефом Киевского гренадерского полка и инспектором украинской дивизии. Император пожаловал ему воинский чин генерала от инфантерии и гражданский — действительного тайного советника. 7 июня 1799 года Павел I зачислил А. А. Беклешова в свою свиту и ввел в Совет при высочайшем дворе.
Князь А. А. Чарторыйский писал о Беклешове: «Это был человек старорусской партии, с виду грубый, но который под весьма грубою внешностию хранил правдивое сердце, твердое и сострадательное к бедствиям других. Его репутация, как благородного человека, была прочно установившаяся. Он сумел сохранить это качество даже во время управления южными губерниями. Там он показал себя справедливым в отношении к управляемым и строгим в отношении к подчиненным. Он противодействовал, насколько мог, воровству, злоупотреблениям, обману. Он не мог терпеть, чтобы его поверенные злоупотребляли правосудием ради своего прибытка. Он вышел чистым и незапятнанным из этого испытания, окруженный признательностью местных жителей. Подобных примеров весьма мало среди высших сановников».
7 июля 1799 года А. А. Беклешов был назначен генерал-прокурором и получил очередную награду — орден Св. Иоанна Иерусалимского. Биограф Беклешова В. С. Иконников писал: «Столь частые перемещения не были участью одного Беклешова… Подобная судьба постигала тогда многих, стоящих на верху правления: награды и опалы, повышения и удаления быстро чередовали друг друга и часто казались необъяснимыми даже для лиц, близко стоящих к среде, окружающей императора».
Назначая очередного генерал-прокурора (а за непродолжительное царствование Павла I их было четверо), император сказал ему: «Ты да я, я да ты, вперед мы одни будем дела делать». Несмотря на такой солидный вексель, выданный монархом (фактическое признание генерал-прокурора вторым лицом в государстве), А. А. Беклешов занимал высший прокурорский пост чуть более полугода.