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