Ревностный католик и сторонник Стюартов, он, однако, провёл почти всю свою жизнь на службе иностранным интересам. Также на российской службе состояли его племянники Александр и Томас.
Его предок королевский адвокат Гордон женился на Маргарэт Лермонт из Балькоми, которая приходится родственницей М.Ю.Лермонтова.
В 16 лет покинул родину и поступил в Браусборгскую коллегию в Данциге, по окончанию которой в июле 1655 года поступил на службу в шведскую армию. Взятый в плен поляками в сражении под Варшавой, перешел на польскую службу и сражался с татарами и русскими. Русский посол в Варшаве Леонтьев заметил способности Гордона и уговорил его вступить на русскую службу.
2 октября 1661 года Патрик Гордон вместе с другим шотландцем, Менезием, прибыл в Москву и был зачислен в иноземный приказ в чине майора. Затем был переведен в полк иноземного строя Кроуфорда подполковником, в 1665 году произведен в полковники и в 1668 году «по государевым делам» послан в Англию.
После этого, Гордон много лет провёл в Малороссии (1667—1686 годы), принимая участие в военном управлении краем. В 1671 году ходил с полком на усмирение бунтующих казаков в Новоскол. В 1673—1675 годах участвовал в военных действиях против Дорошенко.
В 1676 году участвовал в Первом Чигиринском походе и особенно отличился своими работами по устройству предмостного укрепления при Бужинской переправе. Но особенно отличился при руководстве обороной Чигирина в 1678 году (9 июля — 11 августа), за что и был произведен в генерал-майоры.
По окончании войны был назначен в Киев и занялся его укреплением. Произведенный в 1683 году в генерал-лейтенанты, вызвал на себя неудовольствие временщика князя В. В. Голицына, за что был разжалован им в прапорщики, но вскоре был восстановлен в звании с назначением командиром 2-го выборного Бутырского полка. Блестящий смотр, произведенный юным Петром I этому полку 3 февраля 1687 года зародил в нем симпатии к Гордону.
Патрик Гордон участвовал в крымских походах 1687 и 1689 годов.
События 1689 года, способствующие падению царевны Софьи, поставили Гордона в близкие и даже дружеские отношения с царём. 4 сентября в немецкую слободу пришла царская грамота, в которой Петр приказывал иноземным генералам и офицерам прибыть к нему в Троице-Сергиеву лавру. Гордон, как старший из иностранных офицеров, правильно учитывая политический момент, счел правильным идти всем иноземным офицерам в лавру, несмотря на то, как на это отреагируют царевна Софья и князь В. В. Голицын. Но, принимая такое решение, Гордон в то же время признал необходимым, в порядке службы, уведомить о царском указе князя Голицина, и просить формального предписания для следования в лавру. Смущенный Голицын ответил, что он покажет грамоту царю Ивану и царевне и тогда скажет, что делать. Гордон возразил, что когда царю и его семейству грозит опасность, то начальник должен исполнять долг присяги, хотя бы и не получив приказа от вышестоящего начальства. Ввиду этого, не дождавшись до вечера ответа Голицина, Гордон с Бутырским полком, частью 1-го выборного полка и со всеми иноземными офицерами отправился в лавру, куда и прибыл на следующий день. Благодаря этому Петр одержал победу без кровопролития, что заставило его с особой признательностью относиться к Гордону. После Троицкого похода Гордон становится руководителем всех военных занятий Петра. К этому времени ему было уже 54 года.
Он обладал зрелым умом, большими военными познаниями, имел богатый боевой опыт, умел держать войсковые части в строгой дисциплине, был распорядителен и храбр, но в то же время и предусмотрителен, осторожен и скромен. Свои военные практические знания Гордон поддерживал и освежал изучением различных военных сочинений по артиллерии, фортификации, устройству и образу действий войск в различных государствах. Обладая во всех отношениях высокими нравственными качествами, Гордон был любим и уважаем не только обитателями Немецкой слободы в Москве, но и многими из русской знати.
Занятия с царем ведутся им по уже известной системе. Прежде всего, Гордон ведет с царем специальные беседы. Для этих бесед он в течение января и февраля 1690 года часто ездит в Преображенское, а царь, в свою очередь, навещает Гордона. Беседы касаются вопросов устройства содержания и вооружения войск за границей, а также образа действий войск и способа их употребления.
Вторая часть занятий состояла из учений, которые обычно заключались в проделывании приемов с мушкетами и копьями, в стрельбе и в отработке разных способов построения. На этих учениях Гордон обращал особое внимание на стрельбу в цель и действия гренадеров, которых Гордон завел одну роту в своем полку. Учения отдельных полков перешли впоследствии в учения всех выборных полков, а отдельные упражнения пехоты — в совместные учения пехоты и конницы. Венцом занятий Гордона с Петром были маневры. Между всеми маневрами, учениями и беседами царственного ученика с учителем-иноземцем существовала тесная связь. Особенно значительные маневры были устроены в 1691 и 1692 годах.
В 1694 году Гордон участвует в поездке Петра на Белое море, а чуть позже он уже главный руководитель Кожуховского похода. Будучи человеком опытным и знающим военное дело, Гордон, тем не менее, не мог дать Петру правильного теоретического строго научного образования. Беседы его имели скорее справочный характер, а занятия были строго практическими. Тем не менее, знающий, уравновешенный и осторожный Гордон применял правильные методы при практических занятиях, много способствовал развитию у царя выдержки и осмотрительности при решении вопросов военного дела, требовавших основательного знакомства с военной техникой.
В 1695 и 1696 годах участвовал в Азовских походах. Был третьим (после Ф.А. Головина и Лефорта) из генералов, начальствовавших над русскими войсками при осаде Азова, где на него были возложены осадные работы. Гордон был главным инициатором взятия этой крепости (1696 год).
В 1698 году участвовал под начальством боярина Шеина в разгроме мятежных стрельцов под Воскресенским Новоиерусалимским монастырем.
Гордон оставил после себя дневник, охватывающий всю жизнь автора (окончен 31 декабря 1698 года) и написанный по-английски. Он дошёл до нас не весь: 1667—1677 и 1678—1684 годы утеряны. Ныне хранится в военно-учёном архиве Главного штаба. Часть другого английского экземпляра (1684—1698) — в бывшей Императорской публичной библиотеке.
В 1849—1852 годах дневник Гордона с приложением 112 его писем за 1690—1696 годы издан Оболенским и Поссельтом в немецком переводе и с сокращениями (нем. Tagebuch des generalen Patrick Gordon), причём бо?льшая часть текста (события до 1691) — в старом переводе Стриттера, конца прошлого столетия. С этого-то перевода «Чтения Москов. общ. истор. древностей» начали печатать русский перевод. Вышли 1635—1661 годы («Дневник генерала П. Гордона», часть I, Москва, 1892).
Сочинение генерала Гордона сделалось известным по выдержкам, напечатанным в разных изданиях. Дневник Гордона — один из важных источников русской истории конца XVII века. Не только очевидец, но, в основном, и участник описываемых событий, автор отличается точностью и большой объективностью; форма изложения сухая, документальная, с обилием подробностей.
Особенно много даёт труд Гордона для истории войн с Турцией, военного устройства, личности Петра Великого, общественного и хозяйственного быта того времени.
В XIX веке останки Гордона были перезахоронены на Введенском кладбище в Москве.