В 1689 году шведский король Карл XI отобрал земли у лифляндских дворян, и в Стокгольм для переговоров была направлена депутация от прибалтийских земель, в состав которой входил Паткуль. К этому времени он, несмотря на столь необычное «начало» его биографии, сумел дослужиться до чина капитана шведской армии. Как это вышло — остается загадкой. По всей вероятности, шведы считали, что дети не отвечают за деяния своих родителей, и видели в Паткуле весьма незаурядную личность.
Депутация ставила перед королем вопрос о возвращении отобранных им земель. Особенно резкую позицию занял Иоганн Паткуль. Его дерзость и категоричное предъявление своих прав вызвали гнев короля.
Требования депутации не были удовлетворены. В 1692 году Паткуль снова подает королю жалобу от имени лифляндского дворянства с угрозами в адрес шведского правительства. За это в 1693 году он был обвинен в подстрекательстве к бунту. В 1694 году шведский суд приговорил Паткуля к отсечению сначала правой руки, а потом головы.
Богатое имущество Паткуля было конфисковано, сам он спасся бегством в Швейцарию, а затем во Францию. Он пытался ходатайствовать о помиловании перед новым шведским корешем Карлом XII. Но тщетно.
В 1698 году, укрывшись в Саксонии, Иоганн Паткуль решил посвятить свою жизнь борьбе со шведами и сделал основную ставку на курфюрста Августа II, который к тому же в 1697 году был избран королем Польши.
Саксония — одно из крупнейших княжеств Германии — уже в то время была очагом быстрого промышленного роста. Там успешно развивались горное дело, текстильная промышленность, в Мейсене вскоре возникло производство фарфора. Как раз в ту пору организуются первые Лейпцигские ярмарки, которые впоследствии приобрели не только общегерманское, но и международное значение. Княжество являлось древним центром культуры и просвещения: еще в 1409 году был основан университет в Лейпциге, а в 1502 году в другом саксонском городе — Виттенберге.
Паткуль полагал, что Лифляндия могла бы выиграть от вхождения в состав саксонско-польского альянса. Однако он довольно скоро пришел к выводу, что выступать против Швеции можно только объединенными силами нескольких стран, поскольку саксонско-польский союз шведов не одолеет. Паткуль обладал природной способностью устанавливать контакты с людьми, оказывать на них влияние, да к тому же, пользуясь славой человека, дерзнувшего предъявить жесткие требования шведскому королю, он вошел в доверие к курфюрсту и начал внушать ему мысль о необходимости борьбы со шведами.
В ту пору Швеция доставляла беспокойство многим странам Западной Европы. Паткуль сумел провести переговоры с королем Дании и получил от него согласие войти в коалицию для борьбы со Швецией. Такая же работа была проделана им и в Пруссии. Причем Паткуль действовал настолько тонко и конспиративно, что не было допущено никакой утечки информации о проводившихся им тайных переговорах.
Но взоры Паткуля главным образом были обращены к России. Он считал, что если Россия поддержит коалицию, то тогда можно всерьез рассчитывать на успех в борьбе с ненавистной Швецией.
А тем временем русский царь Петр I совершал поездку по странам Европы в составе российского посольства. Петр выступал под именем Петра Михайлова, числившегося бомбардиром Преображенского полка.
Первым пунктом, который наметил посетить Петр, была Рига, находившаяся под контролем шведов. Они не хотели пускать русских в этот город, но Петр проявил настойчивость, и шведы уступили, установив, правда, плотную опеку. Несмотря на то что шведы буквально дышали в затылок каждому русскому, входившему в группу Петра, царь сумел со своими соратниками тщательно обследовать порт и крепость Риги. Поездка по Прибалтике была использована Петром для проведения рекогносцировки, и ему действительно удалось составить представление о силах шведов в этом регионе.
Петр I готовился к схватке с северным соседом, преграждавшим выход России к Балтийскому морю. Но начинать войну со Швецией Россия не могла, поскольку еще шла война с Турцией. Воевать на два фронта России было не по силам.
В 1699 году в Москву приехал Паткуль со своим тайным планом создания коалиции для борьбы со шведами. Петра уговаривать не пришлось, поскольку он сам давно вынашивал идею «укоротить руки» шведскому королю. Русский царь увидел, что Паткуль является толковым человеком, он не только проделал огромную работу по выяснению позиций Саксонии, Польши, Пруссии и Дании, но и сумел склонить монархов этих государств к совместной борьбе со Швецией.
Петр, узнав эпопею Паткуля, убедился, что перед ним человек, чьи личные интересы объективно совпали с государственными интересами России, и это обстоятельство привело к плодотворному альянсу.
В ноябре 1699 года был подписан тайный военный договор между Россией, Польшей, Пруссией и Данией. Петр обещал вступить в войну со Швецией после завершения мирных переговоров с Турцией.