10 марта 1697 года дипломаты выехали из села Никольского и 18 мая прибыли в Кенигсберг. К 16 июня они добрались до Вены, а к 16 августа до Амстердама. Им везде оказывали достойный прием, а Головину вручали подарки. В Вене он получил благословение от монарха и множество памятных сувениров. Он даже стал вторым после А.Д. Меншикова подданным России, возведенным в графский титул Священной Римской империи. Но вся эта пышность лишь отвлекала внимание от главного: никто не собирался помогать русским в осуществлении их главной цели. И как тут не вспомнить о событиях двухвековой давности – о миссии Ивана Фрязина в Рим в 1471 году. Там русское посольство, приехавшее лишь для того, чтобы дать согласие на свадьбу, склоняли к участию в походе на турок. Теперь, через двести двадцать шесть лет, ситуация изменилась: все было наоборот, и Европа неохотно обсуждала совместную роль в борьбе с турками, ограничиваясь устными, ничего не значащими обещаниями.
Вновь дипломату Головину удалось решить задачу только наполовину – на ту половину, которая была связана с торговлей. Вопросы торговли становились сильной стороной этого человека. Кроме того, Головин смог сломать барьер западного недоверия к России, преодолеть политическую изоляцию страны на Европейском континенте, завербовать на русскую службу около 800 инженеров, врачей, офицеров, закупить десятки тысяч ружей со штыками, которых в нашей стране тогда не было. Он и позднее, уже став государственным администратором, продолжал большое внимание уделять материально-техническому обеспечению армии.
Если гора не идет к Магомету, Магомет идет к горе, и для Головина эта миссия, как и все предыдущие, стала кропотливой работой и практическим осуществлением задач. Но о какой-то другой дипломатии в то время и помыслить было невозможно.
Успехи, пусть и не полные, но достойные, не прошли даром. Головина стали назначать на административные должности. Больше его с дипломатическими миссиями не посылали, но поставили руководить Новгородским, Малороссийским, Устюжским, Смоленским, Ямским приказами, Монетным двором, Галицкой четвертью, Палатой серебряных и золотых дел, а также Оружейной палатой. Ответственность и работоспособность Головина были явно оценены по достоинству. 11 декабря 1698 года Головин, не обладавший знаниями и опытом во флотских делах, возглавил Военный морской отдел, после чего набирал кадры для флота и армии, контролировал производство и закупку оружия, транспортные перевозки, то есть опять занимался практической работой. 19 февраля 1699 года, на исходе XVII столетия, он стал начальником Посольского приказа.
Головин оказался человеком современным, даже в бытовых вещах. Он один из первых надел европейское платье, тогда как в России все еще ходили в старорусской одежде и переносили эти привычки на западные рауты. Так, историк Л.И. Бердников пишет, что «к модникам чиновным монарх был весьма снисходителен. Достаточно назвать бывших у него в фаворе Петра Толстого, Бориса Шереметева, Федора Головина, Павла Ягужинского и других, облачавшихся в богатые модные французские костюмы». И далее: «Любопытно, что и те двести московитов из Великого посольства в Европу (1697–1698 годов) также сперва щеголяли в пышных старорусских костюмах. Однако уже в январе 1698 года все участники русской дипмиссии облачаются в европейские одежды. По возвращении же московитов в Россию их европейское платье поначалу воспринимается как щегольское и даже вызывает насмешки современников. Так, князь Федор Ромодановский, узнав, что посол Федор Головин оделся в немецкое платье, назвал его поступок «безумным». И не подозревал Ромодановский, что совсем скоро (12 февраля 1699 года) знаменитые ножницы Петра I будут властно укорачивать полы и рукава стародавних московских кафтанов и ферязей; последуют и законодательные акты, предписывающие под страхом наказания ношение исключительно европейских костюмов…» (Л.И. Бердников «Дерзкая империя»).