После падения царевны Софьи боярин Борис Шереметев присоединился к сторонникам молодого царя Петра Алексеевича. Во время азовских походов в 1695 и 1696 годах он командовал армией, действовавшей на Днепре против крымских татар, и одержал здесь свои первые громкие победы.
В июне 1697 года ближний боярин Шереметев отправился в путешествие в Польшу, Австрию, Италию и на остров Мальту, частично по собственной инициативе, частично имея негласные дипломатические поручения от правительства. Он уехал спустя три месяца после отъезда из Москвы Великого посольства во главе с царем, который надеялся найти в Евро пе союзников для борьбы с турками. В указе, полученном Шереметевым, цель его поездки была сформулирована обтекаемо: «…Ради видения окрестных стран и государств и в них мореходных противу неприятелей креста святого военных поведений, которые обретаются во Италии даже до Рима и до Мальтийского острова, где пребывают славные в воинстве кавалеры». Между строк и здесь читается задача поиска союзников, тем более что Борис Петрович уже обладал некоторым дипломатическим опытом и был знаком с правилами и обычаями Запада.
Его сопровождала группа молодых дворян, в том числе его младшие братья Василий Петрович и Владимир Петрович.
Во время этого путешествия православного русского боярина принял глава католической церкви папа римский, он встречался с австрийским императором Леопольдом, который «говорил с боярином много тайно», с европейскими политиками и аристократами. Борис Петрович имел дружелюбный и общительный характер, знал иностранные языки и умел вести себя в соответствии с правилами, принятыми при европейских дворах.
На острове Мальта его первого из русских посвятили в рыцари древнего военно-монашеского ордена Святого Иоанна Иерусалимского. Это нарушало принятые в Ордене правила – Шереметев был женат и крещен по православному обряду. Грамота о принятии его в ряды мальтийских рыцарей, написанная на пергаменте по латыни и богато декорированная, хранилась в домовом архиве в Фонтанном доме, а ныне находится в Российском государственном историческом архиве. Члены Ордена в качестве отличительного знака носили на цепи белый четырехконечный эмалевый крест. Получил такой крест и Борис Шереметев, и на всех его портретах этот крест присутствует наряду с «кавалерией», полученной позже за военные победы. Принадлежность к Ордену льстила его самолюбию, приближала его к европейской аристократии. И он, плоть от плоти старомосковской боярской аристократии, превратился в человека новой культуры, став верным соратником Петра I.
Домой он вернулся в феврале 1699 года, накануне большой войны со Швецией. В годы Северной войны против Швеции особенно ярко раскрылись его патриотизм и талант полководца. Шереметев принимал участие в этой войне с первых ее сражений.
В 1700 году в бою под Нарвой он командовал дворянской конницей. Русская армия потерпела тогда сокрушительное поражение. Но в декабре 1701 года именно Шереметев со своими войсками принес России первую победу над шведами у деревни Эрестфер, за что получил орден Святого апостола Андрея Первозванного и чин фельдмаршала. Продолжая действовать против войск Шлиппенбаха, он одержал еще более крупную победу над ним под Гуммельсгофом в июле 1702 года. В продолжение двухмесячного похода удалось захватить крепости Мензу и Мариенбург. При взятии Мариенбурга в числе пленных оказалась и Марта Скавронская (будущая супруга Петра I, затем императрица Екатерина I). В сентябре полководец с вой ском вернулся в Псков, он привел с собой множество пленных вражеских солдат и офицеров, а в обозе – 51 орудие и 26 шведских знамен. По поводу побед Шереметева в Прибалтике Петр I писал Ф.М. Апраксину: «Борис Петрович в Лифляндии гостил изрядно; взял городов нарочитых два, да малых шесть, полонил 12 000 душ, не считая служивых…»