Даже с нарвскими недобитками в конце декабря 1700 г. Б. П. Шереметев начинает свои набеги в Прибалтике, положившие начало успехам русского оружия. Приучая свои войска к мысли о возможности бить шведов, Петр не упускает случая нанести им удар. Слабые силы, оставленные Карлом для защиты Эстляндии и Лифляндии, не могли отразить русских войск. В 1701 и 1702 гг. Б. П. Шереметев со своим корпусом опустошил эти области и два раза разбил шведского генерала Шлиппенбаха: в декабре 1701 г. у Эрестфера и в июле 1702 г. у Гуммельсгофа. Первые победы очень радовали Петра. Сам он не принимал постоянного участия в боевых действиях, а оставил на свою долю организацию обороны. Царь ездил из конца в конец по России, но ежегодно появлялся и на театре войны. В 1702 г. Петр из Архангельска без дорог, через леса и болота прошел до Ладожского озера и протащил с собой две яхты. Выйдя к истокам Невы и действуя с корпусом Апраксина, Петр взял здесь шведскую крепость Нотебург. Древние новгородцы ее построили и назвали Орешком. Царь, после овладения, назвал ее Шлиссельбургом, т. е. ключ-городом, подразумевая ключ к морю.
Весной 1703 г. после поездки в Воронеж Петр снова появился на Неве с войсками Шереметева, взял укрепление Пиентанц (вблизи от устья Невы) и основал у моря укрепленную гавань Петербург в мае 1703 г. Место это было выбрано не без расчета: во-первых, восточный берег Финского залива есть ближайший у России пункт Балтийского побережья — о Риге Петр тогда и не мечтал; во-вторых, Нева, на которой основан был порт, представляет конец естественной системы водных путей, идущих из России. Царь очень дорожил новой гаванью, и все дальнейшие военные операции на севере направлялись к тому, чтобы обеспечить обладание Петербургом. С этой целью шло систематическое завоевание южного берега Финского залива: были взяты Копорье, Ямбург, Нарва, а затем и Дерпт. В Финском заливе Петр немедленно строит флот, а в новый порт приглашает иностранные корабли, чтобы тотчас начать торговлю с Западом. Таким образом, было «прорублено окно в Европу». Чтобы его сохранить, Петр предложил Карлу XII мир, соглашаясь на минимальные приобретения в Прибалтике, но тот отказался.
Видя, что существующая военная организация в России частенько пробуксовывает, Петр решает ее изменить. Начиная с 1705 г. главным средством комплектования армии становятся рекрутские наборы. В рекруты разрешалось брать людей, не опороченных какими-либо преступлениями, неувечных, «не дураков» и сначала только холостых, а с 1707 г. — и женатых. Возраст рекрута постепенно повышался: сначала их брали в возрасте от 15 до 20 лет, затем — от 20 до 30. Набор производился по мере надобности и точно определялся специальными указами, где оговаривалось время набора, число, возраст, с кого брать и т. д.
Постоянные наборы, из-за затянувшейся войны требовавшие ежегодно до 40 тысяч рекрутов, делали эту повинность крайне обременительной для населения. Поэтому с 1705 г., сразу после введения рекрутчины, начались массовые побеги рекрутов. Для их предотвращения установили строгий надзор, а после присяги — круговую поруку. С 1712 г. стали клеймить левую руку. За побег рекруты наказывались смертной казнью, кнутом, ссылкой на каторгу. Однако все эти меры мало помогали, и побеги только усилились. Наконец царь понял, что лишь улучшением содержания рекрутов можно улучшить обстановку, и с 1713 г. на это стали обращать самое серьезное внимание.
Недостаток офицеров из русских заставил Петра при формировании первых регулярных полков обратиться к найму иноземцев. В 1702 г. по всей Европе был объявлен манифест царя о вызове на службу в Россию иностранцев всех народностей и религий, за исключением евреев. С течением времени число иностранных офицеров уменьшается, но даже по штатам 1711 и 1720 гг. все равно 1/3 офицеров в каждом полку еще состояла из иноземцев.
Для обучения всей этой массы рекрутов в армии вводятся новые уставы, коренным образом отличавшиеся от уставов времен Алексея Михайловича, так как в них был отображен не только отечественный, но и европейский боевой опыт. С 1706 г., кроме устава А. Вейде и других генералов, стали появляться личные инструкции Петра I, выражавшие понимание им сути военного дела и основных требований высшего управления войсками, предполагавшего принцип единоначалия в армии. Все эти мероприятия, несмотря на свои изъяны, повысили боеспособность армии.
Готовясь завладеть Балтийским побережьем, Петр большое внимание уделяет и флоту. Еще в 1702 г. он поставил на реке Сясь верфь и начал на ней постройку шести фрегатов. Кроме того, работали уже верфи в Лодейном поле, на реке Луга и в Новой Ладоге, а в 1703 г. была основана Олонецкая верфь на реке Свирь. В 1704 г. на левом берегу Невы начали строить Адмиралтейство. В 1705 г. молодой русский Балтийский флот под флагом вице-адмирала Крюйса уже успешно отбил нападение более сильного и опытного шведского флота у острова Котлин. Все это показывало, что русские на Балтику пришли всерьез и надолго.
