Падение Бирона сопровождалось опалой Бестужева: следственная комиссия в январе 1741 года приговорила его к четвертованию, замененному Анной Леопольдовной ссылкой, лишением поместий и кавалерии. Опала оказалась кратковременной — уже в октябре он неожиданно для многих вельмож появился при дворе, ощущавшем острую нужду в опытных дипломатах.
При Елизавете Петровне потребность в услугах Бестужева возросла еще более — вице-канцлер М. Г. Головкин вместе с немецкой камарильей оказался в опале, и Бестужев в это время был единственным дипломатом, способным выполнять обязанности вице-канцлера и освободить не отличавшуюся трудолюбием императрицу от необходимости вникать в тонкую сеть дипломатических интриг европейских дворов.
Сохранившиеся отзывы современников о Бестужеве изображают его человеком неординарным, обладавшим множеством как привлекательных, так и вызывающих неприязнь способностей: умом, трудолюбием, настойчивостью при достижении поставленной цели, умением постоять за себя в обстановке небывало распространенных дворцовых интриг, хамством. Вызывает уважение такая черта, как умение практически в одиночестве противостоять сонмищу противников и в этом противостоянии добиваться успехов. Естественно, облик Алексея Петровича должен быть многоликим, ибо только сочетание привлекательных черт натуры с коварством и беспощадностью давало ему возможность так долго руководить внешней политикой России.
Недолюбливавшая Бестужева Екатерина II характеризовала его так: «…его несравненно больше страшились, чем любили; это был чрезвычайный пройдоха, подозрительный, твердый и неустрашимый по своим убеждениям, довольно-таки властный, враг непримиримый, но друг своих друзей, которых оставлял лишь тогда, когда они повертывались к нему спиной, впрочем, неуживчивый и часто мелочный». В другом месте своих «Записок» Екатерина пополнила перечень неприятных черт характера Бестужева, отметив его умение руководствоваться, как она писала, отвратительным правилом — «разделять, чтобы повелевать. Ему отлично удавалось смущать все умы, никогда не было меньшего согласия и в городе, и при дворе, как во время его министерства». Неприязненный осадок оставил Бестужев и у Е. Р. Дашковой, встречавшейся с ним единственный раз: «Я видела его всего один раз, да и то издали. Меня поразило фальшивое выражение его умного лица…»
М. М. Щербатов в памфлете отказался от описания внешности Бестужева и поделился своими наблюдениями о его интеллекте и нравственности: «Граф Алексей Петрович Бестужев, бывший при императрице Анне кабинет-министром и добрым приятелем Бирону, за которого он и в ссылку был сослан, человек умный, чрез долгую привычку искусный в политических делах, любитель государственной пользы, но пронырлив, зол и мстителен, сластолюбив, роскошен и собственно имеющий страсть к пьянству». Заметим, М. М. Щербатов был единственным современником, обнаружившим в Бестужеве «страсть к пьянству», — ни один из иностранных дипломатов, по долгу службы часто общавшихся с ним, не заметил у канцлера этого порока.
Много новых штрихов в портрет Бестужева внес Станислав Понятовский, секретарь английского посла Уильямса. У него установились интимные отношения с супругой Петра Федоровича Екатериной Алексеевной, и, как ни старалась великая княгиня держать их втайне, они стали известны двору и императрице Елизавете. Было решено прервать компрометирующую малый двор связь высылкой любовника из России — акцией, совершенной не без участия Бестужева. Совершенно очевидно, что к виновнику прекращения любовных утех Станислав Понятовский не мог питать теплых чувств и изобразился ей «страшилищем». «Пока он не оживлялся, он не умел сказать четырех слов подряд и казался заикающимся. Коль скоро разговор его интересовал, он находил и слова, и фразы, хотя очень неправильные, но полные силы и огня, которые извлекал ртом, снабженным четырьмя обломками зубов, и которые сопровождались сверкающим взглядом его маленьких глаз. Выступавшие у него багровые пятна на синеватом лице придавали ему еще более страшный вид, когда он приходил в гнев, что случалось с ним часто, а когда он смеялся, то был смех сатаны. Он понимал отлично по-французски, но предпочитал говорить по-немецки с иностранцами, которые владели этим языком… Как во всем, он был настойчив в том, чего хотел. Он всю свою жизнь был приверженцем Австрии, до ярости отъявленным врагом Пруссии. Вследствие этого он отказался от миллионов, которые ему предлагал прусский король».
Как видим, отзывы современников разноречивы — одни пытались проникнуть во внутренний мир Бестужева, описать непростые черты его характера, другие сосредоточивали внимание на его внешности. Но все современники отмечали у канцлера наличие незаурядных способностей государственного деятеля, его беспощадность к своим противникам. А противников у него было немало, и приходится удивляться, как ему удавалось наносить им нокаутирующие удары, умея держать и ответные.