Путешествие из Лондона в Эдинбург петровский наставник совершил в компании гэльского вождя сэра Юэна Кэмерона оф Лохил[1852], который приезжал к королевскому двору в Лондоне, чтобы подтвердить у короля земельные притязания своего клана[1853]. По прибытию в Шотландию Патрику Гордону оказали свое покровительство предводители его клана: герцог Гордон и граф Эбердин. При посредничестве последних «московитскому шотландцу» удалось установить связи с виднейшими представителями аристократии северного королевства и будущими якобитами: лордом-канцлером Шотландии графом Пертом и его сестрой графиней Эррол, герцогом Куинсберри, видными представителями клана Гордон (Нетермюром и графом Данфермлином), главой клана Огилви (с которым «русский шотландец» был связан по материнской линии) — графом Эрли, главой клана Хэй — графом Эрроллом, а также маркизом Этоллом и подполковником Т. Баханом[1854]. В своем «Дневнике» П. Гордон упоминает, что в течение почти месячного пребывания в столице он практически ежедневно пировал в обществе шотландских «вельмож», где его высоко чествовали[1855].

Поскольку в России не было постоянного британского дипломатического представителя, грамоту британского короля русскому правительству передал нидерландский посол в Лондоне Аорноут ван Ситтерс через голландского резидента в Москве Йохана Виллема ван Келлера[1856]. Яков II просил самодержцев «Всея Великия, Малыя и Белыя России»[1857] уволить со своей службы и отпустить на родину генерал-лейтенанта Патрика Гордона, ввиду того, что тот является его подданным, и в настоящее время король нуждается в опытных военных специалистах[1858]. Хотя формально послание Якова II было адресовано малолетним царям Ивану и Петру, в действительности рассмотрением дела П. Гордона занялись царевна Софья, которая в 1682–1689 гг. фактически правила Россией, и ее главный фаворит князь В.В. Голицын[1859]. Они не желали предоставлять Гордону увольнение по той же причине, что добивался его Яков II. Патрик Гордон был лучшим генералом русской армии, и в Москве не желали лишаться столь опытного полководца[1860]. В ответ на настойчивые челобитные шотландского генерала об отпуске из страны князь В.В. Голицын угрожал разжаловать его в прапорщики и сослать в Сибирь[1861].

Получив отказ русского правительства, Яков II не оставил намерения использовать столь преданного и способного соратника как П. Гордон в интересах британского престола. В ответ на просьбу князя В.В. Голицына прислать в Россию «посла или посланника»[1862] Яков II 25 октября 1686 г. назначил Гордона британским чрезвычайным посланником в Москве[1863]. По традиции, сложившейся в Московии в XVII в., этот дипломатический ранг был вторым по значимости и выше статуса резидента. Таким образом, Патрик Гордон представлял при русском дворе интересы своего монарха на более высоком уровне, чем постоянный агент главной соперницы Англии — Республики Соединенных провинций — резидент барон Й.В. ван Келлер, находившийся в Москве с 1677 г. по 1698 г.[1864]