Генрих Иоганн Остерман родился в Вестфалии, в семействе пастора Иоганна Остермана, и вырос под неусыпными и разумными попечениями образованных родителей умным, любознательным и прилежным юношей. Он еще в раннем возрасте удивлял всех остроумием, тонкими замечаниями о прочитанных книгах и знакомых людях, а также и обширными познаниями. На пятнадцатом году жизни Остерман поступил в Иенский университет, где со всем пылом любознательной натуры посвятил себя наукам. На несчастье, один печальный случай прервал эти занятия, и молодой студент вынужден был покинуть отечество и переехать на жительство в Голландию. Здесь он поступил на службу секретарем к известному мореходцу Корнклию Крюйсу, который в те дни уже готовился, ко уговору лично знавшего его Петра I, перейти па русскую службу. По прибытии в Россию молодой Остерман прежде всего со свойственным немцам прилежанием занялся изучением русского языка, которым в течение двух лет, благодаря отличным способностям, овладел в совершенстве, научившись не только свободно говорить по-русски, но и писать, что в те времена ценилось особенно высоко. В должности-то секретаря Крюйса и узнал его Петр Великий и сразу признал в нем такого именно подходящего человека, который своим знанием шести европейских языков и своим просвещением мог явиться достойным его сподвижником по преобразованию России.
-- Я беру к себе твоего секретаря, он мне нужен, -- таково было решение Петра, высказанное Крюйсу.
Вслед за тем Остерман был определен в посольство в канцелярию с жалованием по двести рублей в год; здесь трудолюбием, благонравным поведением, исполнительностью воли начальства он вскоре резко выдвинулся по службе и приобрел всеобщую любовь и уважение. Его стали принимать в богатые дома вельмож и делать участником излюбленных Петром ассамблей. На одной из таких ассамблей у князя Меньшикова вдовствующая государыня Прасковья Феодоровна, супруга покойного брата Петра, Иоанна Алексеевича, разговорилась со скромным молодым немцем.
-- А как, батюшка, ваше имя? -- спросила она.
-- Генрих, ваше величество, -- был почтительный ответ.
-- Родителя вашего как звали?
-- Иоанном.
-- Так вам следует называться Андреем Ивановичем, -- было простодушное решение царицы Прасковьи.
Такое решение царицы было немедленно сообщено Петру, который, от души посмеявшись переименованию своего чиновника из Генриха в Андрея, усвоил себе, однако, это переименование. Таким образом, и Остерман стал Андреем Ивановичем, и это имя так тесно слилось с его личностью, что и он сам вскоре стал подписываться под всеми правительственными бумагами новым своим именем -- Андрей Остерман.