Верховным командующим этой заново создаваемой армии Петр назначил боярина Бориса Шереметева, в котором причудливым образом переплелись черты, характерные для старой Московии и новой петровской России. Шереметев был двадцатью годами старше царя и принадлежал к одному из древнейших русских родов, однако еще в юности он выступал против старомосковских обычаев. Как-то раз отец отказал ему в благословении за то, что он явился к нему с обритой бородой. В отличие от большинства русских бояр, Шереметев бывал за границей и жадно впитывал новые впечатления. В 1686 году Софья посылала его с поручениями в Польшу к королю Яну Собескому и в Вену к императору Леопольду. В 1697 году сорокапятилетний Шереметев вновь отправился за границу, на сей раз как частное лицо, получив отпуск от службы на двадцать месяцев. Он побывал в Вене, Риме, Венеции, на Мальте и был представлен императору, папе, дожу и великому магистру Мальтийского ордена, который посвятил его в рыцари и наградил Мальтийским крестом. Соотечественники завистливо дивились тому, как горделиво носил он свой орден, и язвительно спрашивали, не сделался ли боярин «мальтийским посланником». Шереметев невозмутимо сносил эти насмешки. Уитворт, новый английский посланник, называл его «учитивейшим человеком во всей стране».

Хотя Петру импонировал интерес Шереметева ко всему европейскому, он все же чаще использовал боярина не на дипломатической, а на военной службе. Дядя Шереметева командовал русской армией при царе Алексее до тех пор, пока не попал в плен к татарам и тридцать лет провел в заточении в Крыму. Сам Шереметев воевал и с поляками, и с татарами. В 1695–1696 годах, когда Петр штурмовал Азов, Шереметев провел успешный отвлекающий рейд в низовьях Днепра, где захватил несколько турецких крепостей. Шереметев был знающим, но осторожным военачальником. Можно было не сомневаться в том, что приказ Петра никогда не рисковать армией, покуда не будет полной уверенности в благоприятном исходе, Шереметев выполнит.

Пока заново собиралась и оснащалась армия, Петр велел срочно укреплять Новгород, Псков и Печерский монастырь близ Пскова. Женщин и детей ставили на работу наравне с мужчинами. Прекратились службы в церквах, поскольку священников, так же как и мирян, привлекли к земляным работам. Расчищая место под новые укрепления, рушили дома и церкви. Чтобы подать пример, Петр лично работал на рытье первого рва в Новгороде. Уезжая, он оставил за себя подполковника Шеншина. Тот же, полагая, что царь вернется не скоро, работу бросил. Когда Петр возвратился и не застал Шеншина, он велел бить его плетьми у раската и отправить в Смоленск в солдаты.

Петр понимал, что в конце концов ему придется преобразовать свое войско в профессиональную, регулярную армию на основе двадцатипятилетней воинской повинности. А пока, несмотря на предпринятые усилия, новое воинство получило незавидную оценку современника в 1701 году: «Людей на службу нагонят множество, а если посмотреть на них внимательным оком, то, кроме зазору, ничего не узришь. У пехоты ружье было плохо и владеть им не умели, только боронились ручным боем, копьями и бердышами, и то тупыми, и меняли своих голов на неприятельскую голову по три и по четыре и гораздо больше. А если на конницу посмотреть, то не то что иностранным, но и самим нам на них смотреть зазорно: клячи худые, сабли тупые, сами скудны и бсзодежны, ружьем владеть никаким неумелые; иной дворянин и зарядить пищали не умеет, а не то что ему стрелять по цели хорошенько. Попечения о том не имеет, чтобы неприятеля убить; о том лишь печется, как бы домой быть, а о том еще молится Богу, чтоб и рану нажить легкую, чтоб не гораздо от нее поболеть, а от государя пожаловану б за нее быть, и на службе того и смотрят, чтоб где во время боя за кустом притулиться, а иные такие прокураты живут, что и целыми ротами притуляются в лесу или в долу.