Наконец, в короткий срок был восстановлен артиллерийский парк. Правда, при литье медных пушек вследствие недостатка меди пришлось использовать колокола церквей и монастырей. Но в чугунных пушках недостатка не ощущалось – металлургические заводы, срочно возведенные в начале столетия, обеспечили армию превосходной артиллерией, и Петр неоднократно будет иметь случай отметить ее высокие боевые качества.
Наибольшие трудности Петр встретил при укомплектовании армии офицерским составом, и прежде всего потому, что в России до XVIII века не было специальных учебных заведений, готовивших военных специалистов. Петр в 1701 году учредил первое такое учебное заведение – Навигацкую школу, где изучались математика, геометрия, тригонометрия, навигация, астрономия. По мнению царя, «не токмо к морскому ходу нужна сия школа, но и артиллерии и инженерству».
Петр воспользовался знаниями выпускников Навигацкой школы и других учебных заведений, созданных вслед за нею, только много лет спустя. Между тем время не ждало, военные специалисты были необходимы в данный момент. И хотя царь знал, что иностранные офицеры проявили себя под Нарвой не лучшим образом, нужда заставила его вновь обратиться к найму военных специалистов за границей. В 1702 году в странах Западной Европы распространялся переведенный на немецкий язык манифест Петра, приглашавший иностранных офицеров на службу в Россию.
5 декабря 1700 года, то есть две недели спустя после нарвского поражения, царь, находясь в Новгороде, велит Борису Петровичу Шереметеву «иттить в даль, для лучшего вреда неприятелю. Да и отговариваться нечем, понеже людей довольно, также реки и болота замерзли, неприятелю невозможно захватить. О чем паки пишу: не чини отговорки ничем».
Шереметев открыл серию побед над шведами. Действовал он пока осторожно, осмеливался вступать в сражения, располагая лишь двойным или тройным превосходством в силах, но на первых порах были важны любые победы, они поднимали моральный дух армии и постепенно освобождали ее от оцепенения после Нарвы.
Первая значительная победа была одержана в самом начале 1702 года. Шереметев во главе 17-тысячного корпуса напал на шведского генерала Шлиппенбаха и наголову разбил его семитысячный отряд у деревни Эрестфер, неподалеку от Дерпта. Здесь полегла половина шведского войска. «Мы можем, наконец, бить шведов!» – воскликнул Петр, получив донесение Шереметева. Победителей царь щедро наградил, отметив всех – от солдата до командующего. Шереметеву Меншиков по поручению Петра повез орден Андрея Первозванного и извещение, что ему присвоено звание фельдмаршала.
С осени 1702-го по весну 1703 года основные силы русских войск были заняты изгнанием шведов с берегов Невы. В этой кампании участвовал и Петр. Военные действия начались с осады Нотебурга, расположенного на острове у выхода Невы из Ладожского озера. Высокие стены толщиной около двух саженей, возведенные у самой воды, многочисленные пушки, господствовавшие над обоими берегами, превращали Нотебург в неприступную крепость. Для ее осады Петр сосредоточил 14 полков. После трехдневной канонады супруга коменданта крепости от имени всех офицерских жен отправила в лагерь русских барабанщика. В реляции этот эпизод описан в присущем Петру шутливом тоне: жены просили фельдмаршала, «дабы могли из крепости выпущены быть, ради великого беспокойства от огня и дыму и бедственного состояния, в котором они обретаются». На что он, бомбардирский капитан Петр Михайлов, галантно ответил гарнизонным дамам: не отваживается передать их просьбу фельдмаршалу, «понеже ведает он подлинно, что господин его фельдмаршал тем разлучением их опечалити не изволит, а естьли изволят выехать, изволили бы и любезных супружников своих с собой вывесть купно».
Дамы, однако, не вняли любезному совету бомбардирского капитана, и непрерывный обстрел крепости продолжался около двух недель. Затем горнисты протрубили атаку, и начался 12-часовой штурм, по отзыву Петра, жестокий и чрезвычайно трудный. Подвиг русских солдат вызвал удивление иностранного наблюдателя: «поистине удивительно, как русские могли взобраться на такую крепость и взяли ее с помощью одних осадных лестниц».
Русские войска овладели древнерусским Орешком. Царь каламбурил, используя созвучие слов «орех» – «Орешек»: «Правда, что зело жесток сей орех был, однако, слава богу, счастливо разгрызен. Артиллерия наша зело чюдесно свое дело исправила». Орешек – Нотебург Петр переименовал в Шлиссельбург (город-ключ), – подчеркивая этим названием ключевое положение города на Неве, открывавшего путь в неприятельские земли.