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