Заинтригованный столь лестными рекомендациями, Леонтьев встретился с Гордоном и пригласил его на русскую службу. Согласие было получено; к Гордону присоединился и будущий Павел Менезий. Дорогой они заехали в Ригу, где Гордон встретил своих земляков, Ландельса и Вальтера Айрта, с которыми служил в шведской армии. Они и еще несколько человек англичан, валлийцев и шотландцев по окончании войны оказались в Риге без новых контрактов и подыскивали место новой службы. Мистер Стальное Запястье позвал их с собой в Московию, и вскоре вся эта компания отправилась в дорогу-
Как было условлено заранее, Менезий и Гордон получили назначение в полк Кроуфорда, соответственно в чине капитана и майора. Полк сначала квартировал у Красных ворот, но потом его перевели в слободу Огородники, где они встали на обывательских квартирах — между Мясницкой и Покровкой. Под команду Гордона отдали 700 русских солдат и несколько офицеров, часть из которых были русскими. Рядовые были из числа штрафованных — большей частью из дезертиров, пойманных в разных местах и возвращенных в полк. Гордон основательно за них взялся и гонял на учения дважды в день.
Постепенно Менезий и Гордон обжились в Москве, втянулись в службу, стали принимать участие в местных забавах — так, Гордон в июне 1662 года выиграл на скачках, сорвав куш в изрядную по тем временам сумму 100 рублей, которые, впрочем, почти целиком ушли на угощения и пиры для тех, кто приходил поздравить его с удачей.
Упоминание о скачках, сделанное в дневнике Гордона, открывает нам неожиданную сторону московской жизни той поры — даже в Париже, при дворе французских королей, первые скачки на призы состоялись 23 февраля 1689 года. Судя же по записи в дневнике Гордона, в Москве скачки проводились за двадцать шесть лет до этого, а вероятно, и того раньше, поскольку Стальное Запястье упоминает о них как о деле вполне обычном, в котором он просто принял участие и выиграл.
Среди приятелей, приобретенных Гордоном и Менезием в Москве, был шотландец Айвен Аннанд, который прежде служил в армии и даже имел чин капитана, но предпочел оставить службу ради более выгодных занятий медициной в русской столице. Свели их весьма прискорбные обстоятельства: как-то раз, зайдя в гости к Менезию, Гордон излишне приналег на вареную щуку и водку, переел и расхворался. Для пользы лечения с полковой квартиры Гордона перевезли в Немецкую слободу, в дом полковника Снивенса, где его окружили заботами семейство Кроуфорд и хирург Аннанд, взваливший на себя обязанности врачевания.
Мистер Аннанд, как и другие московские знакомые шотландцев, уже давно жившие в Москве, без устали твердил Гордону и Менезию, которые считались завидными женихами, что им пора жениться.
В Немецкой слободе брачные интриги были одним из самых ярких и насыщенных эмоциями развлечений. Окрутить вновь прибывших на жительство в слободу холостяков было своего рода спортом, многодневным действом, за ходом которого следили десятки заинтересованных глаз. Созерцатели делились на партии, каждая из которых «болела» за свою кандидатку в супруги, всячески стараясь ей помочь «устроить судьбу». Тайно принимались даже ставки на то, кто из претенденток сумеет увести под венец очередной объект брачной охоты.
Первым из двух друзей-шотландцев капитулировал осажденный сватами Павел Менезий, который женился в 1662 году. Вслед за ним стал склоняться к мысли о законном браке и Гордон, решивший подобрать себе суженую из офицерских дочерей, справедливо полагая, что люди одного с ним сословия и примерно равных доходов охотнее его примут. Перебрав несколько кандидатур, он остановился на Катарине Бокховен — дочери Филиппа Альберта ван Бокховена, который вместе с отцом и братом, как мы помним, прибыл в Москву еще при царе Михаиле, обжился и осел здесь, похоже, навсегда.
С будущей невестой Гордона свел Аннанд. Отец девицы в это время пребывал в плену у поляков, попав туда в ходе той же кампании, что и полковник Кроуфорд. Его брат Корнелиус ван Бокховен тоже угодил в плен, но ему удалось освободиться при посредничестве посла Леонтьева, как Кроуфорду и многим другим. В 1662 году Корнелиус уже был в Москве.
