После Петра I у его преемников, вплоть до Елизаветы Петровны, не было самостоятельной внешнеполитической программы. Правительство Екатерины I в начале 1725 г. объявило о своей верности общему внешнеполитическому курсу, определенному Петром Великим, а также ранее принятым Россией международным обязательствам. В Европе в это время шла активная подготовка к созданию Венского и Ганноверского союзов. Екатерина I первоначально склонялась к союзу с Францией и Англией. Одной из причин такого выбора служила позиция австрийского императора Карла IV в вопросе о русском престолонаследии. Император выступал за объявление наследником престола царевича Петра Алексеевича, своего внучатого племянника и внука Петра I, что вызывало серьезное недовольство Екатерины I и мешало русско-австрийскому сближению.
Остерман вместе с канцлером Головкиным выступал в Верховном тайном совете за присоединение России к Венскому союзу Австрии и Испании. Он справедливо считал, что Ганноверский союз «против Цесаря, а больше против нас прямо учинен». От русских резидентов в Вене, Берлине, Стокгольме, Копенгагене, Гааге поступала исчерпывающая информация о целях ганноверских союзников, а также о начавшихся летом 1725 г. переговорах английских и французских дипломатов с целью присоединения к ним Швеции и Дании. Важным источником информации была весьма влиятельная группа доброжелательных к России чиновников в шведском правительстве. Они не только информировали русского посланника Н. Ф. Головина о дипломатических акциях ганноверских союзников, но и принимали контрмеры, стремясь убедить правящие круги Швеции в невыгодности присоединения к Ганноверской лиге.
Правительство Екатерины I пыталось оказать противодействие антирусской политике англо-французской дипломатии. С целью упрочения русских позиций и достижения более тесного русско-шведского союза в апреле 1726 г. Верховный тайный совет решил направить в Стокгольм специальное посольство во главе с В. Л. Долгоруким. Перед ним была поставлена задача заключить новый союзный договор со Швецией, чтобы сорвать ее переговоры с ганноверскими союзниками и не допустить присоединения к этому блоку. Учитывая состояние дел в Швеции и «нынешние деликатные конъюнктуры», было решено ассигновать до 100 тыс. рублей для подкупа шведских государственных деятелей. Но посольство Долгорукова из-за различных причин прибыло в Стокгольм лишь в начале ноября, и время было упущено. Сразу же по приезде Долгорукий отметил ослабление позиции «доброжелательных» и усиление влияния их противников. В декабре 1726 г. состоялась встреча Долгорукова со шведским королем и главой правительства графом Арвидом Горном, которая закончилась безрезультатно. Обещание посла удвоить или даже утроить размеры взятки тоже не помогло. «Лехче муфтия в христианский закон ввести, нежели удержать шведов от присоединения к Ганноверской лиге», — с горечью признавался Долгорукий.
В сложившейся ситуации серьезным ударом по Ганноверскому союзу стало сближение России и Австрии. Г. И. Головкин, А. И. Остерман, В. Л. Долгорукий, действуя против А. Д. Меншикова, Ф. М. Апраксина и Д. М. Голицына, отстояли заключение союза с Австрией. 26 июля (6 августа) 1726 г. в Вене был подписан русско-австрийский оборонительный и наступательный союзный договор. Россия и Австрия выступили совместно в двух важнейших войнах 30-х гг.: в войне за польское наследство и в турецкой войне 1735–1739 гг.
После смерти Екатерины I и воцарения в мае 1727 г. Петра II Остерман, используя свое влияние на молодого императора, во многом способствовал падению своего соперника князя А. Д. Меншикова в сентябре 1727 г. Изворотливость и осторожность помогли Остерману сохранить свое высокое положение и после смерти Петра II в январе 1730 г.
Андрей Иванович, сказавшись больным, не принял участия в заседании Верховного тайного совета, избравшего преемницей покойного императора герцогиню Курляндскую Анну Иоанновну и принявшего «кондиции» об ограничении самодержавия. Анна Иоанновна, безропотно подписавшая «кондиции» в Митаве, прибыв в Москву, обнаружила, что «затейка» верховников не пользуется поддержкой ни у большинства дворян, ни у гвардейцев. Она публично надорвала лист бумага с подписанными ею «кондициями». Этим самым курляндская герцогиня провозгласила себя самодержавной императрицей. Среди тех, кто поддержал Анну Иоанновну, был и Остерман. В благодарность императрица назначила Андрея Ивановича в марте 1730 г. сенатором. В апреле 1730 г. Остерман был возведен, с нисходящим его потомством, в графское Российской империи достоинство и получил земли в Лифляндии.
Ленивая и малообразованная Анна Иоанновна не проявляла никакого интереса к государственным делам. Вместо упраздненного Верховного тайного совета при ней было организовано примерно такое же по компетенции учреждение, но под новым названием — Кабинет министров. В ноябре 1731 г. Остерман, в звании второго кабинет-министра, вошел в состав Кабинета. С 1733 г. он председательствовал в Военно-морской комиссии «для рассмотрения и приведения в добрый и надежный порядок флота, адмиралтейства и всего, что к тому принадлежит». Ничего не смысля в морском деле, Остерман дослужился в России до чина генерал-адмирала.
В 1734 г., после смерти Г. И. Головкина, Андрей Иванович получил звание первого кабинет-министра и возглавил российскую дипломатию. Обладая тонким умом и большим дипломатическим опытом, Остерман прекрасно разбирался в сложных хитросплетениях европейской политики. Чрезвычайно осторожный в принятии решений, он, тем не менее, хорошо усвоил основные элементы внешнеполитического курса Петра I. Следуя этому курсу, Остерман стремился избежать борьбы на два фронта, при этом ради решения наиболее жизненно важных задач он не останавливался перед значительными жертвами. Так, вопрос о взаимоотношениях с Персией Андрей Иванович подчинял более важной и сложной турецкой проблеме. Он не верил в возможность удержания Гиляна и других завоеванных областей во время Каспийского похода Петра I и готов был возвратить их, чтобы приобрести в Персии союзника против Турции. В начале 1732 г., следуя указаниям А. И. Остермана, П. П. Шафиров подписал с Персией Рештский договор, содержавший пункт о возвращении ей провинций Гилян, Мазендеран и Астрабад. В 1735 г. при участии Андрея Ивановича Россия и Персия заключили Гянджинский договор об оборонительном союзе. По этому договору Россия вернула себе Баку и Дербент.
В 1735 г. Россия вступила в войну с Турцией. В этой ситуации русское правительство особенно интересовала позиция Швеции. Важным успехом русской дипломатии стало восстановление в августе 1735 г. военно-политического союза со Швецией. Союзником России в русско-турецкой войне была Австрия. Однако Вена затягивала переговоры о военной помощи России, и только в январе 1737 г. была подписана конвенция о совместных военных действиях против Турции. В середине того же года по инициативе Турции была предпринята попытка мирного урегулирования русско-турецкого конфликта. С 16 августа по 11 ноября в украинском местечке Немирово состоялся конгресс русских, турецких и австрийских представителей. Русскую делегацию возглавили П. П. Шафиров, А. П. Волынский и И. И. Неплюев. Работой делегации руководил А И. Остерман. Руководствуясь инструкцией Остермана, русская делегация предъявила свои требования. Это были не столько пожелания России в настоящем, сколько программа ее восточной политики в будущем.
Требования России не только встретили резкие возражения со стороны турок, но и встревожили австрийцев, предъявивших претензии на часть Молдавии и Валахии, Сербии и Боснии. Австро-русские противоречия укрепили позиции Турции, которая готовилась к развертыванию наступления на Балканах. В итоге Немировский конгресс закрылся. Война продолжалась еще два года. После выхода Австрии из войны в 1739 г. в Белграде был заключен и русско-турецкий мирный договор. Перед угрозой шведского нападения Остерман решился на заключение мирного договора, далеко не соответствовавшего затраченным Россией усилиям. Тем не менее, договор развязал России руки для предотвращения шведского нападения на Петербург, которое было отсрочено этим на два года.