Но подлинную славу стяжали ему баталии Северной войны 1700–1721 годов. Под Нарвой (в 1700-м) Шереметев командовал конницей, которая успешно действовала против крымцев, хотя и не устояла перед натиском войск Карла XII. Первые впечатляющие победы были одержаны им в Прибалтике, где он, с 1701 года фельдмаршал и кавалер ордена Святого Андрея Первозванного, взял Эрестфер (1701), Гуммельсгофе (1702), Копорье (1703), Дерпт (1704). В легендарном Полтавском сражении (1709) Борис Петрович руководил всей пехотой русской армии, а в 1710 году командовал осадой Риги вплоть до ее капитуляции.
Шереметеву довелось пережить и все тяготы Прутского похода 1711 года, в результате которого он потерял сына Михаила, оставленного, согласно договору с османами, в турецком плену на три года (он скончался по пути домой). Он и сам часто подвергал себя смертельной опасности, бросаясь в самое пекло битвы. Однажды он поспешил на помощь солдату, которого теснили трое турок, и спас его. Борис Петрович командовал наблюдательной армией против Турции в 1712–1714 годах, а 1715–1717 годах – корпусом в Мекленбурге и Померании.
Шереметев удостоился чести стать первым русским кавалером мальтийского ордена Большого Креста с бриллиантами, который 10 мая 1698 года на острове в своем дворце вручил ему сам Великий магистр ордена. В пространном сопроводительном патенте говорилось о «знаменитости рода и доблести» новоиспеченного кавалера, но прежде всего – об «услугах Христианству», оказанных «Великим Государем, Его Царским Пресветлейшим Величеством» Петром I. Так Борис Петрович заручился поддержкой Мальтийского рыцарского ордена в борьбе России с Турцией и Крымским ханством.
Когда, по возвращении в Москву, Шереметев, украшенный полученным на Мальте орденом, предстал перед царем, монарх принял его милостиво, поздравил с награждением и приказал всегда носить этот орденский крест. А в Разряде и в присутственных местах повелел записать: «что титло его сверх боярского достоинства еще получено приращение, и как в Боярской книге, в Росписях и других бумагах, так и сам бы он писал: боярин и военный свидетельствованный мальтийский кавалер». Слово «свидетельствованный» показывает, сколь похвальным казалось в глазах монарха признание заслуг его подданного европейскими «политичными» кавалерами.
Судьбе было угодно, чтобы Борис Петрович не только сам обрел новый европейский облик, но и отчаянно расправился с его противниками и гонителями. Так, в 1705 году в Астрахани местные жители подняли бунт против ретивого воеводы, проявлявшего непомерное рвение в исполнении царских указов о брадобритии и немецком платье. Вверенные ему солдаты и стрельцы ловили на улицах Астрахани бородачей и тут же отрезали у них бороды, прихватывая иногда и кожу; ножницы шли в ход и для укорачивания старорусской одежды.
Как потом показали на следствии заговорщики, они «сходились меж собою о том, чтоб учинить бунт, воеводу и начальных людей побить, и за веру и правду постоять, и усов и бород не брить, и немецкого платья не носить». Подобные же мотивы приводились бунтовщиками в советном письме от 31 июля 1705 года, посланном в Черкасск донским казакам, которых они надеялись привлечь на свою сторону. Однако поскольку царские указы о брадобритии и немецком платье на казаков не распространялись, те не только не присоединились к астраханцам, но взяли под стражу их посланцев и, заковав в кандалы, отправили в Москву. Таким образом, требования смутьянов – длиннополое платье, борода и усы – символизировали старину и выражали протест против прогресса и европеизации страны. А подобная ретроградность локализовала восстание, препятствовала перерастанию отдельного эпизода в событие общероссийского значения. Тем не менее бунт был опасен и требовал от правительства карательной операции.
И для роли руководителя такой операции у Петра не было лучшей кандидатуры, чем Шереметев. В самом деле, для этого не подходили ни Александр Меншиков, которого бунтовщики считали виновником нововведений («Все те ереси от Меншикова да жителей Немецкой слободы»), ни князь Федор Ромодановский, ни Федор Головин, ни Федор Апраксин, также непосредственно причастные к новшествам, вводимым в стране. В этом отношении Борис Петрович, всецело занятый борьбой с внешними врагами и не участвовавший в преобразованиях Петра I во внутренней жизни державы, был наиболее подходящей фигурой в силу своей нейтральности.
Вначале Шереметев обещал восставшим полное прощение, но бунтовщики не пожелали покориться. Тогда фельдмаршал двинул на Астрахань всю свою трехтысячную армию и взял город штурмом – признав поражение, восставшие выставили у городских ворот плаху с топорами. За подавление восстания Петр I – впервые в России – пожаловал Борису Петровичу в 1706 году титул графа.