Родоначальником фамилии Паткуль геральдисты называют вассала ордена меченосцев Андреаса Паткуль, жившего в Риге в 1385 году. Род Паткуль был внесён в Лифляндский и Эстляндский (в 1746 году) матрикулы.
Иоганн фон Паткуль родился в Стокгольме в тюрьме, куда мать его сопровождала своего мужа, осужденного за сдачу полякам города Вольмар.
Иоганн фон Паткуль состоял на шведской военной службе дослужился до чина капитана, в 1689 году был членом лифляндской депутации, которая просила у Карла XI о восстановлении прав и привилегий лифляндского дворянства. Паткуль действовал при этом с такой прямотой и настойчивостью, что возбудил ненависть короля Карла XI. В 1692 году он вновь потребовал от правительства в Риге прекратить зоупотребления, и за резкое осуждение действий правительства был отослан в Стокгольм, где приговорён в 1694 году к отсечению правой руки и конфискации имущества, но успел бежать в Курляндию. Заочно его приговорили к смерти за покушение на восстание в Лифляндии, нарушение воинской дисциплины и дезертирство. Он удалился в Швейцарию под именем Фишеринга и там попробовал посвятить себя наукам. После этого ездил в Италию и Францию.
После того, как ходатайства перед новым шведским королем Карлом XII об отмене приговора остались тщетными, Паткуль поступил в 1698 году на службу к курфюрсту саксонскому и королю Польши Августу Сильному и в 1698 году был посвящен в тайные советники. Будучи послан в Москву, способствовал заключению Преображенского союзного договора между Саксонией, Польшей и Россией против Швеции. В 1700 году будучи генерал-маором участвовал в осаде Риги и при приближении небольшого шведского корпуса бежал.
Не поладив с приближёнными курфюрста, Паткуль в 1702 году перешёл на службу к Петру I. Весь поглощённый мыслью о мести шведскому королю, о пользе России он вовсе не думал и во многом шёл вразрез с намерениями Петра. Царь, например, призывал на службу иностранцев для того, чтобы русские от них научились военному или дипломатическому искусству. Паткуль находил, что русские не приготовлены ни к чему и поэтому их следует заменять иностранцами. Отсюда целый ряд жалоб Паткуля на русских офицеров и солдат и их жалоб на самого Паткуля. Много вредил Паткулю и его характер — жёсткость, резкость, высокое мнение о себе и низкое о других.
В 1702 году он выпросил себе командование русскими корпусом при саксонско-польской армии.
В 1704 году Паткуль был послан Петром I в Варшаву в качестве русского министра и вслед за тем был назначен начальником русского отряда, посланного на помощь Августу. При содействии этого отряда Август вернул себе Варшаву, которая была занята шведами; затем Паткуль бесплодно простояв целый месяц под Познанью, также занятой шведами, 24 октября, так и не решившись на штурм, снял осаду и отвёл войска на зимние квартиры в Саксонию.
В своих донесениях оттуда Паткуль постоянно жалуется на недостаток денег, на дороговизну всех припасов, грозит покинуть царскую службу, упрекает Петра в том, что тот не пришёл в Польшу. В то же время Паткуль с обычной своей резкостью неоднократно высказывал своё мнение о неспособности самого короля Августа и его министров, которые и воспользовались первым удобным случаем, чтобы погубить Паткуля. Пётр приказал Паткулю или вывести войска из Саксонии в Россию через Польшу, или, если это окажется невозможным, передать их временно на службу австрийскому императору и затем вернуться через Венгрию. Паткуль решился на последнее.
В 1705 году в Дрездене, Паткуль решился жениться на богатой вдове датского посланника в Саксонии и удалиться в свое купленное в Швейцарии имении, когда в день свадьбы был арестован и отвезен в крепость Зонненштейн. Саксонский тайный совет, управлявший государством, потребовал, чтобы Паткуль оставил войска в Саксонии. Когда Паткуль на это не согласился так как он должен был передать войска австрийскому императору, министры решили арестовать его (20 декабря 1705), ссылаясь на то, что Паткуль действует самовольно, без ведома царя и тайных сношениях со Швецией. Истинной причиной ареста было недоверие к нему со всех сторон и знание им политических тайн.
Около двух лет Пётр I многократно протестовал против такого нарушения международного права, но внимание его было отвлечено опасностью, угрожавшей в то время России со стороны Швеции. По Альтранштедтскому миру между Швецией и Саксонией (1706) Паткуля решено было выдать Карлу XII. Август II тайно приказал коменданту крепости Кенигштейн дать Паткулю возможность бежать; но вследствие жадности коменданта, который непременно хотел получить с Паткуля выкуп, дело затянулось до тех пор, пока в крепость вступил шведский отряд, и 7 апреля 1707 года Паткуль был закован в цепи. 10 октября он был, как изменник, колесован живым, а затем четвертован.
Несчастная судьба Паткуля вдохновила многих поэтов, в том числе Ивана Тургенева, Гуцкова. Его вывел на сцену и И. И. Лажечников в романе «Последний Новик».