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