Наибольшие трудности Петр встретил при укомплектовании армии офицерским составом, и прежде всего потому, что в России до XVIII века не было специальных учебных заведений, готовивших военных специалистов. Петр в 1701 году учредил первое такое учебное заведение – Навигацкую школу, где изучались математика, геометрия, тригонометрия, навигация, астрономия. По мнению царя, «не токмо к морскому ходу нужна сия школа, но и артиллерии и инженерству».

Петр воспользовался знаниями выпускников Навигацкой школы и других учебных заведений, созданных вслед за нею, только много лет спустя. Между тем время не ждало, военные специалисты были необходимы в данный момент. И хотя царь знал, что иностранные офицеры проявили себя под Нарвой не лучшим образом, нужда заставила его вновь обратиться к найму военных специалистов за границей. В 1702 году в странах Западной Европы распространялся переведенный на немецкий язык манифест Петра, приглашавший иностранных офицеров на службу в Россию.

5 декабря 1700 года, то есть две недели спустя после нарвского поражения, царь, находясь в Новгороде, велит Борису Петровичу Шереметеву «иттить в даль, для лучшего вреда неприятелю. Да и отговариваться нечем, понеже людей довольно, также реки и болота замерзли, неприятелю невозможно захватить. О чем паки пишу: не чини отговорки ничем».

Шереметев открыл серию побед над шведами. Действовал он пока осторожно, осмеливался вступать в сражения, располагая лишь двойным или тройным превосходством в силах, но на первых порах были важны любые победы, они поднимали моральный дух армии и постепенно освобождали ее от оцепенения после Нарвы.

Первая значительная победа была одержана в самом начале 1702 года. Шереметев во главе 17-тысячного корпуса напал на шведского генерала Шлиппенбаха и наголову разбил его семитысячный отряд у деревни Эрестфер, неподалеку от Дерпта. Здесь полегла половина шведского войска. «Мы можем, наконец, бить шведов!» – воскликнул Петр, получив донесение Шереметева. Победителей царь щедро наградил, отметив всех – от солдата до командующего. Шереметеву Меншиков по поручению Петра повез орден Андрея Первозванного и извещение, что ему присвоено звание фельдмаршала.

С осени 1702-го по весну 1703 года основные силы русских войск были заняты изгнанием шведов с берегов Невы. В этой кампании участвовал и Петр. Военные действия начались с осады Нотебурга, расположенного на острове у выхода Невы из Ладожского озера. Высокие стены толщиной около двух саженей, возведенные у самой воды, многочисленные пушки, господствовавшие над обоими берегами, превращали Нотебург в неприступную крепость. Для ее осады Петр сосредоточил 14 полков. После трехдневной канонады супруга коменданта крепости от имени всех офицерских жен отправила в лагерь русских барабанщика. В реляции этот эпизод описан в присущем Петру шутливом тоне: жены просили фельдмаршала, «дабы могли из крепости выпущены быть, ради великого беспокойства от огня и дыму и бедственного состояния, в котором они обретаются». На что он, бомбардирский капитан Петр Михайлов, галантно ответил гарнизонным дамам: не отваживается передать их просьбу фельдмаршалу, «понеже ведает он подлинно, что господин его фельдмаршал тем разлучением их опечалити не изволит, а естьли изволят выехать, изволили бы и любезных супружников своих с собой вывесть купно».

Дамы, однако, не вняли любезному совету бомбардирского капитана, и непрерывный обстрел крепости продолжался около двух недель. Затем горнисты протрубили атаку, и начался 12-часовой штурм, по отзыву Петра, жестокий и чрезвычайно трудный. Подвиг русских солдат вызвал удивление иностранного наблюдателя: «поистине удивительно, как русские могли взобраться на такую крепость и взяли ее с помощью одних осадных лестниц».

Русские войска овладели древнерусским Орешком. Царь каламбурил, используя созвучие слов «орех» – «Орешек»: «Правда, что зело жесток сей орех был, однако, слава богу, счастливо разгрызен. Артиллерия наша зело чюдесно свое дело исправила». Орешек – Нотебург Петр переименовал в Шлиссельбург (город-ключ), – подчеркивая этим названием ключевое положение города на Неве, открывавшего путь в неприятельские земли.

В середине марта Петр прибыл в Шлиссельбург для руководства военными действиями в кампании 1703 года. В апреле царь сообщает Шереметеву о готовности войск начать операцию: «и больше не могу писать, только что время, время, время, и чтоб не дать предварить неприятелю нас, о чем тужить будем после». Речь шла о нападении на Ниеншанц – крепость, запиравшую устье Невы. После осмотра Ниеншанца Петр поделился впечатлениями с Меншиковым: «Город гораздо больше, как сказывали; однакож не будет с Шлютельбурх. Про новой вал сказывали, что низок, который выше, неже город сам, и весь зачат и выведен равно изрядною фортификациею, только лише дерном не обложен, а ободом (т. е. окружностью) больше Ругодева» (Нарвы). Гарнизон Ниеншанца сложил оружие, не дожидаясь штурма. 2 мая Петр писал в Москву «князю-кесарю» Ромодановскому: «Известую вашему величеству, что вчерашнего дня крепость Ниеншанская по 10 часной стрельбе из мартиров (также из пушек только 10-ю стреляно) на акорт здалась». И тут же распоряжение: «Извольте сие торжество отправить хорошенько и чтоб после соборнова молебна из пушек, что на площади, было по обычаю стреляно».

У Ниеншанца же три дня спустя состоялось первое боевое столкновение с неприятельским флотом. Два шведских судна из эскадры Нумерса, не зная о капитуляции Ниеншанца, вошли в устье Невы. Петр решил их атаковать. Под его пером операция выглядела следующим образом: 5 мая «пришла на устье неприятельская шквадра под правлением вице-адмирала господина Нумберса; о чем уведав, наш господин фельтмаршал посылал нас в тритцати лотках. И в 7 день, пришед к устью, гораздо осмотрели неприятеля, и по нарочитом бою взяли 2 фрегата, один Гедан о десяти, другой Астрил о восьми пушках, а окон четырнатцать. Понеже неприятели пардон зело поздно закричали, того для солдат унять трудно было, которые, ворвався, едва не всех покололи; только осталось 13 живых. Смею и то писать, что истинно с восемь лодок только в самом деле было».

Атака кораблей примитивными лодками, экипажи которых располагали лишь ружьями и гранатами, была связана с большим риском. Надо было обладать огромной отвагой, чтобы решиться на это предприятие. Петр рисковать не любил, предпочитал действовать наверняка, и благополучно окончившаяся операция, кажется, была единственной, где царь отступил от своего правила.

В последующие годы к подобного масштаба выигранным сражениям привыкли настолько, что хотя и отмечали их салютами, но считали будничными событиями ратной жизни. Эта победа привела Петра в неподдельный восторг, ибо она была первой на воде. Он ее и назвал «никогда бываемою викториею». Она положила начало славным боевым традициям русского военно-морского флота.

По приказанию Петра в архиве даже производились специальные разыскания – не происходило ли что-либо подобное в давно прошедшие времена. Петр поспешил уведомить друзей об одержанной победе, отправив письма. Содержание этих, как и многих других, писем и реляций с извещением о победе раскрывает существенную черту Петра. Царь пишет «мы», «нас», «наши войска», «ударили на неприятеля», «получили викторию», причем множественное число употребляет отнюдь не применительно к собственной персоне, как это делали монархи до и после него. Для него «мы» значит «русские войска». Сам автор писем при этом оставался в тени, в тексте нет ни строчки о его действиях и распоряжениях, определивших исход победоносного сражения. Зато сообщаются подробнейшие сведения о трофеях, захваченных пленных, потерях противника и об уроне, понесенном русскими войсками. Этим сухим перечнем Петр как бы приглашал своего корреспондента оценить степень удачи, сопутствовавшей русским войскам, и размеры катастрофы, постигшей неприятеля.