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