Во время первого Азовского похода 1695 г. Шереметев возглавил армию, действовавшую против турецких крепостей на Днепре. Борис Петрович оказался удачливее царя и его сподвижников. В кампании 1695 г. русско-украинское войско взяло у турок три крепости (30 июля – Кызы-Кермень, 1 августа – Эски-Таван, 3 августа – Аслан-Кермен). Имя Шереметева стало известно всей Европе. При этом Азов так и не взяли. Нужна была помощь союзников. Летом 1696 г. Азов пал, но этот успех показал, что дальнейшая война с Османской империей возможна только при объединении усилий всех стран – участниц «священной лиги».
Пытаясь угодить царю, Борис Петрович по собственной воле и за свой счет отправился в путешествие по Европе. Боярин покинул Москву через три месяца после отъезда на Запад самого Петра и путешествовал более полутора лет, с июля 1697-го по февраль 1699-го, истратив на это 20 500 рублей – огромную сумму по тем временам. Истинная, так сказать, человеческая цена подобной жертвы становится понятной из характеристики, данной Шереметеву известным советским исследователем эпохи XVIII века Николаем Павленко: «…Борис Петрович бескорыстием не отличался, но не отваживался красть в масштабах, дозволяемых себе Меншиковым. Представитель древнейшего аристократического рода если и воровал, то настолько умеренно, что размеры украденного не вызывали зависти у окружающих. Но Шереметев умел попрошайничать. Он не упускал случая напомнить царю о своей «нищете», и его стяжания являлись плодом царских пожалований: вотчин он, кажется, не покупал…»
Проехав через Польшу, Шереметев вновь побывал в Вене. Затем направился в Италию, осмотрел Рим, Венецию, Сицилию, и, наконец, добрался до Мальты (получив аудиенции за время поездки у польского короля и саксонского курфюрста Августа, императора Священной Римской империи Леопольда, папы римского Иннокентия XII, великого герцога тосканского Козимо III). В Ла-Валетте его даже посвятили в рыцари Мальтийского ордена.
Таким европейским «шлейфом» не мог похвастаться еще ни один россиянин. На следующий же день после возвращения, на пиру у Лефорта, одетый в немецкое платье с мальтийским крестом на груди Шереметев смело представился царю и был им с восторгом обласкан.
Однако милость оказалась недолгой. Подозрительный «герр Питер», согласно вскоре изданному «боярскому списку», опять повелел Борису Петровичу отправляться подальше от Москвы и быть «у города Архангельского». Вновь вспомнили о нем лишь через год, с началом Северной войны (1700–1721 гг.). Война началась в августе походом главных сил русской армии к Нарве. Боярин Шереметев был назначен командующим «поместной конницы» (конного дворянского ополчения). В нарвском походе 1700 г. отряд Шереметева действовал крайне неудачно.
