Службу при дворе царя Алексея Михайловича он начал стольником в 1661 году. Он сопровождал царя в поездках по монастырям и царским селам или стоял рындой на его торжественных приемах. В 1679 году он был назначен в Большой полк товарищем воеводы. Спустя два года получил место на должность воеводы недавно организованного Тамбовского разряда.
В 1682 году, по случаю восшествия на престол царей Петра и Иоанна, Шереметев был пожалован в бояре. Это делало его членом Боярской думы и давало возможность принимать личное участие в управление государственными делами.
В период борьбы между Петром и Софьей Борис Петрович одним из первых поддержал Петра. С тех пор он стал ближайшим сподвижником молодого государя, хотя всю жизнь между ними сохранялась определенная дистанция. Выходцу из старинного аристократического рода претило много нового, появившегося в обычаях русского царя, что шло вразрез с его представлениями о царском величии. Не импонировало ему и то, что Петр I окружал себя людьми из «подлых» фамилий, мало считаясь при этом с интересами фамилий древних. Он так и не смог до конца приспособиться к новому двору.
Но при том в нем проявилось иное качество, во многом чуждое новому окружению царя – близость к солдатской массе. Боевые действия русских войск под командованием Шереметева во многом напоминали черты военного искусства предшествующего столетия – они отличались медлительностью, осторожностью, отказом от рискованных операций.
В 1695 году Петр I поручил Шереметеву формирование 120-тысячной армии для предполагавшейся войны с Турцией. Конечной целью новой войны должен был стать Азов. Шереметев, уже имевший опыт борьбы с Крымом, пытался предупредить царя о рискованности этого предприятия. Все же он смог сформировать армию и повести ее в поход. В том же году армия Шереметева взяла хорошо укрепленный Кизы-Кермень на Днепре. Это так испугало турок, что они без боя оставили еще три укрепленных городка. И все же, не желая рисковать, Шереметев не пошел на Крым, а повернул на Украину.
В 1697—1699 годах Борис Петрович находился в Европе, выполняя дипломатические поручения.
Как полководец Шереметев приобрел широкую известность в годы Северной войны. С января 1700 года он уже назывался «генералом» и начальником «дворянской нестройной конницы». В сентябре его войско было под Нарвой, где через два месяца русские войска потерпели жестокое поражение. Однако отношение Петра к своему генералу не изменилось, и две недели спустя после Нарвского сражения он поручил ему идти в шведские земли и нанести сколько возможно вреда противнику.
В декабре 1701 года Шереметев принес России первую победу над шведами в сражении у села Эрестфер. За эту победу Шереметев был награжден орденом Св. Андрея Первозванного и был произведен в фельдмаршалы. Продолжая действовать против войск Шлиппенбаха, он одержал еще более крупную победу над ним под Гуммельсгофом в июле 1702 года. В продолжение двухмесячного похода удалось захватить крепости Мензу и Мариенбург. При взятии Мариенбурга в числе пленных оказалась и будущая жена царя Марта Скавронская (будущая императрица Екатерина I). В сентябре Шереметев с войском вернулся в Псков, ведя с собой свыше тысячи пленных солдат и офицеров, 51 орудие и 26 знамен.
Осенью, двинувшись к устью Невы, войска Шереметева овладели крепостью Нотебург. Петр переименовал Нотебург в Шлиссельбург («Ключ-город») и отпраздновал его взятие торжественным парадом войск через триумфальные ворота в Москве. А в следующем году были взяты Ниеншанц, Копорье, Ямбург и Везенбург. Таким образом, в 1703 году войска фельдмаршала Шереметева завоевали землю древней Ингрии с выходом к Балтийскому морю.
В апреле 1704 года по приказу Петра к Дерпту был направлен корпус под командованием Шереметева. Взяв город, фельдмаршал успел еще и содействовать царю в овладении Нарвой.
Уже осенью 1704 года Шереметев получил приказ Петра I отправиться во главе корпуса русской конницы против корпуса генерала Левенгаупта, находящегося в Литве. После прибытия в Витебск Шереметев обнаружил, что фураж для лошадей отсутствует, и решил не выходить в поход до тех пор, пока он не будет доставлен в войска. Раздосадованный поведением своего фельдмаршала, Петр прислал в Литву Меншикова, доставившего Шереметеву указ о переподчинении части его войска, прежде всего пехоты, фельдмаршалу Георгу Огильви, недавно нанятому на царскую службу. Конница по-прежнему оставалась под командованием Шереметева, но русский фельдмаршал был чрезвычайно недоволен создавшимся положением, ведь фактически своим указом Петр создавал в армии двоевластие.
Среди серии побед были у фельдмаршала Шереметева и военные неудачи. Так, в сражении у Мур-Мызы он потерпел поражении от корпуса Левенгаупта, но вскоре, приведя войска в порядок, Шереметев вновь перешел в наступление. Это было единственным поражением Шереметева за годы Северной войны, но оно скоро было забыто из-за новых побед, одержанных под руководством самого Петра I.