Впервые будущий канцлер оказался за границей в 15-летнем возрасте. В 1708 г. вместе с такими же дворянскими недорослями повелением Петра I он был направлен на учебу в Копенгаген и Берлин. Завершив курс, путешествовал по Европе, совершенствовал знание языков и вникал в извивы европейской политики, после чего в 1712 г. был определен на дипломатическую службу.
Его становление прошло под опекой Б.И. Куракина, талантливого дипломата, возглавлявшего русское посольство в Голландии. Затем четверть века он представлял Россию в Дании, Голландии, Англии. Его работа за рубежом выпала на период дворцовых переворотов, когда периодическая смена правителей приводила к возвышению одних царедворцев и опале других. Бестужеву-Рюмину удалось избежать и взлетов, и падений, он лишь перебирался в новую страну, становясь все более искушенным в дипломатических и придворных интригах. Попутно ему удалось получить чин тайного советника и стать кавалером ордена Св. Александра Невского.
Знание тонкостей большой политики очень пригодилось ему, когда в 1740 г. он был вызван в Санкт-Петербург и из сравнительно тихой дипломатической заводи попал в водоворот борьбы за власть в окружении императрицы Анны Иоанновны. Всесильному фавориту Э. Бирону удалось свалить кабинет-министра А.П. Волынского и отправить того на эшафот. Освободившаяся должность была предложена Бестужеву-Рюмину. Поскольку Алексей Петрович не был ранее связан ни с какими группировками, Бирон, вероятно, надеялся опереться на него в борьбе против вице-канцлера А.И. Остермана, которого рассматривал как еще одного злейшего врага.
Но эти планы нарушила кончина Анны Иоанновны. Через непродолжительное время Бирон был смещен и отправлен в ссылку. С привлеченного к следствию по его делу Бестужева-Рюмина подозрения сняли быстро, но от службы отставили.
К активной внешнеполитической деятельности на самом высоком уровне его призвала Елизавета Петровна. «Дщерь Петрова» походила на своего венценосного отца еще и дальновидностью. Она хорошо понимала, какую роль может сыграть опытнейший чиновник, имевший в свои 48 лет тридцатилетний дипломатический стаж. Осенью 1741 г. Бестужев-Рюмин был приближен к особе новой императрицы и обласкан ею: удостоился ордена Св. Андрея Первозванного, получил место сенатора и пост вице-канцлера.