Тем временем в июле Август повел свои саксонские войска на повторный штурм Риги, чтобы уже в сентябре окончательно признать поражение и отправить армию на зимние квартиры к югу от города. Однако тогда русские стали представлять более серьезную опасность для Карла, поскольку они прекратили войну с турками. Хотя раньше это останавливало царя Петра от объявления войны Швеции, теперь, заключив мир с султаном, он был готов присоединиться к союзникам. В октябре его войска угрожали шведским территориям и после вторжения в Ингрию начали осаду Нарвы, стратегически важной крепости в шведской Эстонии.
В ответ Карл немедленно перебросил войска на помощь осажденным. Через пять дней после отплытия из Карлскруны, сквозь сильный шторм, в котором пострадали и люди, и лошади, 25 сентября (6 октября) его армия переправилась в Пернов (Пярну) в Рижском заливе. Получив известие о том, что угроза со стороны Августа миновала, Карл позволил своей армии оправиться после такого путешествия и переключил внимание на защиту своей крепости на севере. С наступлением зимы армия двинулась по раскисшим дорогам в Ревель, оттуда – в Везенберг (совр. Ра́квере), примерно в 110 км от их цели. Здесь король планировал ждать подкрепления, но вскоре, переживая за осажденный гарнизон, решил больше не мешкать. После еще одной недели пути по труднопроходимой сельской местности, опустошенной русскими, его измотанные и полуголодные люди достигли Нарвы 19 (30) ноября. Как показывают расчеты, в то время как шведская армия насчитывала около 9000 человек, силы русских включали в себя порядка 35 000–40 000 человек. Более того, они хорошо окопались в два ряда: окопы огибали крепость дугой к реке, которая защищала крепость с другой стороны. Поскольку их расположение было явно безопасным, русское командование не ожидало нападения небольшой шведской армии, предполагая, что шведы тоже выроют окопы и создадут еще один ряд укреплений. К их удивлению, в два часа дня Карл приказал начать штурм. К этому времени разыгралась снежная буря, но погода была только на руку шведам, ослепляя их противников. Когда шведы прорвались через центр вражеских укреплений, перебив всех на своем пути, русские солдаты в панике бежали к реке. Многие утонули, некоторые были сметены лошадьми при попытке перейти вброд, другие оказались в воде, когда рухнул мост, не выдержав большого скопления людей. Поскольку бо́льшая часть русской армии не имела достаточной подготовки, основные бои закончились спустя три часа, и, хотя какое-то время гвардейские полки Петра еще держались, они согласились сдаться в плен еще до окончания ночи. В то время как офицеры были взяты в плен, солдатам разрешили сложить оружие и отступить, поскольку русская армия была слишком велика, чтобы Карл мог оставить всех в плену.
Король участвовал в самой гуще сражения, дважды потеряв во время битвы лошадей, и теперь его почитали за отвагу и умение повести за собой. Об этой победе, одержанной над многократно превосходящими силами противника при сравнительно небольших потерях шведов, заговорила вся Европа. В то время как среди шведских солдат этот успех принес Карлу репутацию непобедимого, у самого короля он вызвал пренебрежение к русским войскам и недооценку их потенциала, что в итоге привело шведского правителя к краху. Однако пока он столкнулся с более серьезной проблемой. После битвы измученные солдаты Карла заняли брошенные вражеские палатки для желанного ночлега, не зная, что многие русские солдаты болели. В течение нескольких последующих дней и недель болезнь распространилась по шведскому лагерю, многие умерли. Короля болезнь обошла стороной, но в будущем он больше не совершал подобной ошибки, предпочитая ночевать под открытым небом вне зависимости от погоды.
Как только прошла зима и его армия оправилась, Карл начал готовиться к встрече со своим следующим врагом – Августом. В июле 1701 г. он прибыл в Дюнамюнде, где осуществил успешную переправу через Западную Двину (Даугаву), использовав лодки и плоты для переправы солдат через реку. Опираясь на опыт, полученный в Нарве, Карл приказал зажечь на авангардном судне влажную солому, используя попутный ветер, чтобы ослепить дымом врага. Достигнув переправы, он разбил саксонскую армию, которую Август привел в страну, – недавно избранный король еще не получил разрешения сейма использовать польские войска, – и с отступлением саксонцев Карл беспрепятственно двинулся в герцогство Курляндское.
К декабрю 1701 г. беспокойство Августа нарастало, и теперь он пытался убедить шляхту Варшавы поддержать его и позволить использовать польские войска в борьбе со шведами. Потерпев здесь неудачу, в следующем году он прибегнул к другому плану, послав свою бывшую любовницу Марию Аврору фон Кенигсмарк попытаться убедить Карла XII согласиться на его щедрые предложения мира. Король Польши ее очень любил, она была матерью одного из немногих признанных Августом незаконнорожденных детей, Морица Саксонского, и, хотя ей было почти сорок, все еще славилась своей красотой и обаянием. Тем не менее Карл отказался с ней встретиться; ей даже не удалось привлечь его внимание, когда она обратилась к Карлу, преклонив колени перед ним на дороге. Повернувшись к ней спиной, он уехал, а позже выразил свое отвращение к подобным женщинам, устраивая облавы солдатских спутниц, отправляя их на проповедь о благочестии, а затем изгоняя из лагеря. Август не сдался и продолжал предлагать мир, но Карл отклонял их вопреки советам своих министров. Презирая своего брата за его предательство и порочный образ жизни, король был полон решимости отстранить Августа от власти. Собираясь уговорить поляков свергнуть их короля, Карл вошел в Варшаву, но прежде, чем были достигнуты какие-либо соглашения, Август вопреки условиям, согласованным при его избрании, снова вошел в Польшу во главе своей саксонской армии. Когда оба кузена встретились при Клишове, шведский король одержал очередную победу над превосходящим противником. На сей раз его завоевания не обошлись без личных потерь: муж его сестры, Готторпская Фурия, оказался среди трехсот убитых со шведской стороны. Тем не менее данный военный успех дал возможность Карлу двинуться дальше и взять Краков.
Продолжая подозрительно относиться к Августу, Карл наконец убедил польский сейм свергнуть короля и заменить его одним из своих дворян Станиславом Лещинским. Несмотря на противостояние других соперничающих представителей шляхты, многие из которых намеренно бойкотировали выборы, в следующем году молодой человек короновался в Варшаве как Станислав I. Август при поддержке русских отказывался признать поражение, поэтому военные действия продолжались еще два года, Карл совершал зигзагообразные маневры по Польше, захватывая города и одерживая победы в очередных сражениях. В итоге, решив вторгнуться в Саксонию, в сентябре 1706 г. он прибыл в Альтранштедт близ Лейпцига. Многие, включая жену и мать короля, бежали в страхе за свою жизнь, но, когда ситуация разрешилась, многие вернулись. К концу месяца Карл уже составлял договор для подписания Августом, по которому тот официально отказывался от польского престола и признавал нового короля.
Этот договор включал дополнительное условие. Карл настоял на выдаче Иоганна Паткуля, честолюбивого лифляндского дворянина, который хотел добиться независимости своей страны от Швеции. Паткуль, ранее объявленный отцом короля предателем, на время бежал за границу и вернулся на территорию Швеции только после смерти Карла XI, в надежде получить прощение от нового короля. Поскольку эту просьбу отклонили, Паткуль предложил свои услуги Августу, действуя какое-то время как доверенное лицо в переговорах с царем Петром. По условиям договора Август теперь обязался выдать его, и шведы немедленно казнили Паткуля за измену. Несмотря на мольбы о помиловании младшей сестры Карла, король остался непреклонным и полным решимости отомстить человеку, осмелившемуся выступить против шведской короны, а также предупредить всех, кто собирался последовать примеру Паткуля. По приказу Карла казнь была жестокой. После того как Паткуля колесовали, его четвертованное тело выставили на всеобщее обозрение и убрали только шесть лет спустя, после возвращения на престол короля Августа. Хотя отныне Карла боялся народ, его осуждали и за границей, даже царь Петр, который сам поступал не лучшим образом, добавил свой голос к всеобщему возмущению. Хотя шведский король требовал дисциплины от своих войск, сдерживая грабеж на полях битвы в соответствии с законами того времени, тем не менее под его командованием войска часто действовали с невероятной жестокостью, и сам он проявлял совершенную безжалостность. В некоторых случаях Карл был великодушен к своим пленникам и предоставил провизию сдавшимся, но выжившим и голодавшим после осады Торна, но, как правило, он был безусловно хладнокровен, мало заботясь о побежденных. Он не гнушался призыва к жестоким репрессиям и резне целых сообществ, которые оказывали сопротивление его войскам.
В последние дни перед подписанием договора Август отчаянно торговался с союзниками. Даже во время мирных переговоров он тайно налаживал контакты с русскими, которые, в свою очередь, не знали о его сделке с Карлом. Однако, когда генерал Петра Меншиков прибыл со своей армией в Калиш, Август в последний момент осознал, какую опасную игру ведет, и попытался остановить боевые действия, сообщив шведскому командованию о мире, который должен был быть вскоре подписан. Не имея другого подтверждения этому и с подозрением относясь к Августу, шведский генерал А.А. Мардефельт отказался верить этой информации. Вместо этого, под давлением своих польских союзников, он решил вопреки здравому смыслу вступить в бой с противником, и поэтому всего через несколько дней после того, как соглашение было достигнуто, 18/29 октября 1706 г., началось сражение. Шведы уступали числом, а бегство многих из них с поля боя только усугубило их положение. В течение трех часов Меншиков одержал громкую победу, в результате которой в плен попало 5000 шведов и поляков и погибло около 2000 человек. Тем не менее, хотя известие об этом разгроме сильно разозлило Карла, который снова обвинил своего кузена в коварстве, к концу ноября отречение Августа стало общеизвестным, а вскоре двоюродные братья встретились в Альтранштедте. Теперь, когда договор был подписан, Карл решил остаться в городе почти на весь следующий год, присматривая за отдыхом и пополнением своих войск, а также используя возможность посетить поле битвы неподалеку, где погиб его предшественник Густав Адольф.