После «завоевания» Азова в 1696–1697 годах Шереметев находился в дипломатической поездке по Европе под именем ротмистра Романа. Выполнял царские поручения, доставив послания австрийскому императору Леопольду I, папе римскому Иннокентию XII, дожу Венецианской республики и Великому магистру (гроссмейстеру) Мальтийского ордена. После этой поездки ближний боярин стал известен в европейских столицах. Там были наслышаны и о том, что он умел воеводствовать при отражении набегов на русские пределы конницы Крымского ханства.
Потом скажут, что Борис Петрович Шереметев «очаровал Европу». Он проявил себя в этой поездке не только как блистательный дипломат, понимающий премудрости дворцовых интриг, способный, никого не обижая, но и никому не угождая, отстаивать интересы Отечества, и как щедрый вельможа, не кичившийся своим личным богатством.
Правда, европейское турне для Шереметева началось с того, что петровскому посланцу пришлось вырываться из замка польского магната Радзивилла, который к числу друзей Московии не относился. Зато польский король Август II (Август Саксонский) встретил царского боярина с большими почестями. Так его принимали и в Вене, и в Вечном городе, то есть в Ватикане, в Неаполе, Флоренции и Венеции.
На Мальте царский посланник склонял местных рыцарей, как в Вене императора Священной Римской империи, к совместным действиям против Оттоманской Порты. Великий магистр (гроссмейстер) ордена Раймунд-Переллос-Рокафулл возложил на боярина Б.П. Шереметева Мальтийский командорский крест, причислив его, таким образом, к числу рыцарей ордена.
Более того, Великий магистр вверил русскому посланнику командование двумя галерами, которым предстояло действовать против турок-османов. Но повоевать тогда на море Борису Петровичу не довелось: дела посольские требовали от него торопиться с возвращением в Москву. Царь Петр I там его заждался.
В отечественной истории это был первый случай награждения подданного России иностранным орденом. Можно заметить, что в Европе тогда орденских наград было, как говорится, раз-два и обчелся. Петр I специальным указом внес в официальный титул Шереметева ни у кого не встречающийся титул «свидетельствованного мальтийского кавалера».
Путешествие Б.П. Шереметева по ряду европейских государств было не чем иным, как поиском вероятных союзников петровскому царству в противостоянии с Оттоманской Портой. Взятие Азовской крепости и появление новопостроенного русского флота на Азовском море не открывало России выхода на морские торговые пути. Проливы Босфор и Дарданеллы оставались в руках турок, и только силой европейского сообщества можно было открыть их для свободного мореплавания, в том числе и для россиян.
Царь Петр I, посылая в Европу боярина-воеводу, хотел с его понимания больше знать о состоянии там военного дела. Борис Петрович исподволь интересовался всем, что интересовало государя: состояние крепостей и фортификационное дело, новшества в артиллерии и обучении войск, возможности производить закупки новейшего оружия (ружей и прочего), развитие кораблестроительного дела.
В том дипломатическом путешествии, которое закончилось на Мальте, Борис Петрович проявлял необычайную щедрость. Всюду, куда он попадал, раздавались богатые подарки, прежде всего «мягкой рухлядью» – драгоценными соболями и другими мехами Русского Севера. На эти цели, как известно, царский тайный посол потратил из собственных средств 25 тысяч рублей. Государь же остался доволен миссией Шереметева.
В Москву Шереметев 12 февраля 1699 года привез то, чего ожидал от этой поездки царь Петр I: европейские политики одобряли решение российского монарха драться со шведами и продолжать священную войну с иноверцами, то есть с Оттоманской Портой. Последнего от Московии особенно желали Вена и Венеция, Рим и Мальта. Но в тех столицах, где побывал петровский посланец, конкретной помощи особо не обещали, зато обещали в вызревшем конфликте на севере европейского континента оставаться нейтральной стороной. Это было для Петра I, в те дни усиленно занимавшегося законодательством, крайне важно.
Ближний боярин Б.П. Шереметев многое сделал для того, чтобы в Северной войне Россия не осталась без союзников и без доброжелательного отношения к ней в ряде европейских столиц. С началом же войны ему пришлось оставить дипломатическое поприще и сразу стать большим военачальником у царя Петра I. Собственно говоря, у царя среди своих подданных особого выбора не виделось: «иноземного строю не знали».
В преддверии войны со Швецией, когда государственная казна пустовала из-за огромных расходов царства на создание регулярной армии, ее вооружения и снаряжения, Петр I был много благодарен боярину Борису Петровичу вот еще за что. Дворецкий Шереметева, ездивший с ним в Италию, Алексей Курбатов, тоже интересовавшийся жизнью чужеземных стран, заметил там много из того, что в России еще не зналось. Именно Курбатов предложил «орлиную бумагу».