При Павле I происходит некоторое сокращение численности прокуроров. Вначале с закрытием верхних земских судов и верхних расправ, а затем и губернских магистратов были упразднены и состоявшие при них прокуроры. Беклешов как генерал-прокурор выполнял самые разнообразные функции. Административные, судебные, военные, финансовые, хозяйственные и прочие дела — все были в поле его зрения.
Хотя назначение Беклешова генерал-прокурором и воспринималось современниками положительно, недоброжелателей у него было более чем достаточно. По свидетельству современников, он был человеком светлого ума, весьма сведущим в государственном управлении, отличался безукоризненной честностью и правдивостью, но был очень «несдержан в словах и отзывах своих». Не умея укрощать пылкого своего нрава, он был тяжел и не всегда приятен в служебных отношениях, хотя гнев его никогда не был продолжительным.
В своих «Записках» русский поэт, баснописец и государственный деятель И. И. Дмитриев писал, что Беклешов, не имея опыта своих предшественников, был в то же время очень трудолюбив. Он охотно и терпеливо выслушивал доклады и объяснения обер-прокуроров и почти всегда утверждал их заключения. Другой видный сановник, М. М. Сперанский, работавший с четырьмя генерал-прокурорами павловского времени, писал: «Беклешов был их всех умнее, но и всех несчастнее — ему ничего не удавалось».
2 февраля 1800 года Павел 1 неожиданно уволил Беклешова не только с должности генерал-прокурора, но и вовсе со службы. По мнению М. М. Сперанского, причина такой перемены заключалась в том, что Беклешов «мало уважал требования случайных людей при дворе и потому часто бывал с ними в размолвке».
А вот что писал по этому поводу барон Гейкинг: «Должность генерал-прокурора есть одна из тех, влияние которой распространяется на все государство и внушает такой же страх в Камчатке, как в Курляндии или в Петербурге… Выбор нового генерал-прокурора повсюду был встречен с удовольствием. Находясь в Петербурге, я познакомился с ним, но только поверхностно, однако был очень рад его назначению, будучи убежден, что он пойдет прямою дорогою. Вдруг о Беклешове стали, как бы случайно, поговаривать в неблагоприятном смысле; а так как он показывал, что не обращает на это внимания, то опала его была решена. Стали делать ему тысячи неприятностей, и так как он, кроме того, осмелился противоречить государю по поводу судебных решений, то его стали попрекать в учительском тоне, в тяжеловесном и неприятном ведении дел».
Вступивший на престол Александр I вновь призвал А. А. Беклешова на службу и вернул ему пост генерал-прокурора (16 марта 1801 года), который тот занимал вплоть до образования министерств (8 сентября 1802 года). В день коронования Александра I он получил орден Св. Андрея Первозванного. По мнению Г. Р. Державина, в первый год царствования Александра I именно Беклешов вместе с Трощинским, бывшим в то время статс-секретарем, и Воронцовым имели наибольшее влияние на молодого императора и «ворочали государством».