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