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