Но поражение под Нарвой не привело Петра в уныние. Он понимал, что враг превосходил русских не числом и мужеством, а умением вести войну. «Войне не конец, войне только начало», — заявил Пётр и стал спешно перестраивать армию. За короткое время в армию были взяты тысячи новых рекрутов. Вместо дворянской конницы и стрелецкой пехоты Пётр организовал драгунские (кавалерийские) и армейские (пехотные) полки. Он создал лёгкую полевую артиллерию и вооружил ею конницу. В артиллерии были введены новые образцы орудий — пушки, гаубицы и мортиры. В Москве было открыто военное училище для подготовки офицеров. Дворяне должны были поступать на военную службу солдатами и постепенно выдвигаться в офицеры. На Урале, где были найдены залежи руды, спешно строились новые заводы. В декабре 1701 года домна на Невьянском заводе выдала первую партию чугуна для пушек. Пётр велел снять даже колокола и перелить их на пушки.
На заводах отливались ядра и пушки, ковались сабли. На верфи у Лодейного Поля закладывались военные корабли. Пётр внёс много нового и в военную тактику. Он требовал взаимодействия артиллерии с конницей и пехотой, поощрял активность и инициативу солдат и командиров всех родов оружия.
Результаты переустройства армии сказались быстро. В январе 1702 года русские войска недалеко от Юрьева (Тарту) разбили шведского полководца Шлиппенбаха. Это была первая победа над шведами, которых до этого считали непобедимыми.
Летом того же года русские солдаты очистили от шведов Ладожское и Чудское озёра, а осенью после десятидневной бомбардировки штурмом была взята шведская крепость Нотебург (Орешек). «Зело жесток сей орех был, — писал Пётр, — однакож, слава богу, счастливо разгрызен». Нотебург был переименован в Шлиссельбург, что значит «Ключ-город». Он стал ключом для выхода России к морю.
Весной 1703 года под ударами русских войск пала шведская крепость Ниеншанц в нижнем течении Невы.
Пётр спешил укрепиться на Неве, которая открывала выход в Балтийское море. На острове Котлине, расположенном у входа в Неву, была заложена крепость Кроншлот (впоследствии Кронштадт). Тогда же на одном из островов в устье Невы среди болот и лесов началась закладка новой русской крепости, впоследствии названной Петропавловской. Против крепости Пётр построил для себя небольшой деревянный домик. Рядом с ним построили свои дома и многие приближённые Петра. Так возник Петербург — будущая столица государства.
Пётр правильно учёл и умело использовал ошибку Карла XII, недооценившего боевые качества русских войск. Он стал отвоёвывать старинные русские земли. В 1703 году были взяты Ям и Копорье. В 1704 году — Юрьев, а также крепости Ивангород и Нарва. Однако главные силы шведов ещё не выступали против русских. Шведский король бросил их в это время против Польши. Когда Пётр предложил ему мир, надменный Карл гордо заявил: «Пусть наш сосед Пётр строит города, мы сохраним за собой славу их завоёвывать».
Но Петр предвидел другое. «Шведы могут еще раз-другой побить нас, — говорил он. — Но у них же мы научимся побеждать их». Русская армия приобретала боевой опыт. Она готовилась к решающему сражению.
В 1706 году Карл XII разбил польского короля Августа II, занял Краков и Варшаву и двинулся в глубь русской территории. Мечтая о мировом господстве, шведский король надеялся захватить Москву, расчленить Россию и подчинить её шведскому владычеству. Первоначально Карл выбрал прямой путь на Москву через Смоленск — «ворота Москвы».
Считаясь с военным превосходством противника, Пётр приказал отходить на восток, ослабляя врага «малой войной», то-есть боевыми действиями мелких отрядов. Сопротивление оказывали не только арьергарды отступавшей русской армии, но и всё население. Жители сёл и городов прятали продовольствие и скот в лесах, жгли хлеб и фураж, нападали на арьергарды и одиночных шведских солдат.