В 1655 году Патрик вступил в войско шведского короля Карла X, но через год в сражении с поляками попал в плен и освобожден при условии вступления в польскую армию. В том же году он вновь попал в плен теперь уже к шведам и перешел к ним на службу.
Все похождения Гордон отмечал в своих «Записках». Он рассказал, что его дружина прославилась грабежами, да и сам он промышлял разбоем: у двух крестьян отнял лошадей. Денег наемным офицерам не платили. В 1658 году Гордон вторично оказался в польском плену, а с 1661 года перешел на русскую службу в чине майора. Патрик Леопольд в 26 лет оказался в России и стал именоваться Петром Ивановичем.
Глава Иноземного приказа Илья Милославский потребовал, чтобы вновь прибывший показал умение пользоваться копьем и мушкетом. Патрик возразил, что это дело денщика, а офицер должен уметь командовать солдатами. Но Милославский настоял на своем и остался доволен майором, назначив ему подарок за поступление на российскую службу 25 рублей деньгами и на 25 рублей соболями. Однако дьяк подарков не выдавал, хотя Гордон несколько раз обращался к нему. Гордон надумал покинуть Россию и только тогда получил причитающееся.
Он выступал в защиту солдат, которые были в его подчинении, отражал нападения стрельцов, имел поединок с майором Монтгомери, поссорившись с ним на пирушке. В 1676 году Гордон — уже подполковник — был втянут в новый конфликт с генералом Трауернихтом, который подговорил драгун подать на него жалобу. Но Патрик уже успел зарекомендовать себя способным офицером, и жалоба была отвергнута.
Он участвовал в подавлении Медного бунта (1662 год), неофициально находился с дипломатической миссией в Англии. За 15 лет его положение в Немецкой слободе упрочилось, он стал признанным, уважаемым человеком, как среди иностранцев, так и военных, признававших его умение руководить полками нового строя.
Когда юный Петр познакомился с Немецкой слободой, первыми его друзьями стали Лефорт и Гордон, получивший в 1683 году чин генерал-лейтенанта. Со своим Бутырским полком в 1689 году он пришел на выручку к Петру в борьбе с Софьей, а в 1690—1694 годах руководил его военным обучением.
Генерал участвовал в Азовских походах, в 1693 году стал контр-адмиралом русского флота. Гордон добился открытия католической церкви. Он постоянно стремился узнавать все новое в военном деле, в механике, картографии, чтобы усовершенствовать русскую армию. Из прожитых 64 лет Патрик Гордон без малого 40 лет честно служил России, стал одним из сподвижников молодого Петра.