В кампании 1695 года русско-украинское войско взяло у турок три крепости (30 июля – Кызы-Кермень, 1 августа – Эски-Таван, 3 августа – Аслан-Кермен). Имя Шереметева стало известно всей Европе. При этом Азов так и не взяли. Нужна была помощь союзников. Летом 1696 года Азов пал, но этот успех показал, что дальнейшая война с Османской империей возможна только при объединении усилий всех стран – участниц Священной лиги.
Петр ясно понимал, что Османская империя легко не смирится с потерей Азова. А выход на черноморский простор требует еще более серьезной кампании. Без сильных союзников здесь не справиться.
Необходимо искать союзников в Европе. Лучше всего создать антитурецкую коалицию в Юго-Восточной Европе. Для этого надо было договориться с основными политическими игроками. Признанный лидер европейских государств того времени – Франция и её король Людовик XlV были заняты борьбой за испанский престол. Польский король Ян Собеский умер в 1696 году, что значительно снизило антитурецкие позиции в Польше. Поэтому Пётр планировал посетить Варшаву, Вену, Ватикан и Венецию. Венеция в данном случае рассматривалась как место с непревзойденными строителями морских галер, которых Пётр планировал использовать на первом этапе войны и строительства кораблей. Амстердам и Лондон рассматривались как столицы ведущих морских держав. Особое место уделялось Мальтийскому ордену, имеющему большие навыки вооруженного противостояния Османской империи.
Летом 1698 года в самое, может быть, необычное государство Европы, созданное на острове Мальта рыцарями Суверенного военного ордена госпитальеров Святого Иоанна, прибыл посланец Петра I – Петр Андреевич Толстой. Боярин по поручению царя изучал ратное дело. Глава ордена – Великий магистр – разрешил ему осматривать оборонительные сооружения острова и оснастку боевых кораблей. Толстой даже принял участие в морском сражении с турками, о чем ему было выдано соответствующее свидетельство. Этот боевой опыт был, может быть, самым главным в его поездке: Петр искал в лице ордена христианских воинов-рыцарей будущих союзников в борьбе с магометанами. Не успел стольник Толстой вернуться в Москву, как на Мальту прибыл еще один русский корабль – на этот раз с посольством, возглавляемым ближним боярином царя Борисом Петровичем Шереметевым. Его миссия была составной частью «Великого посольства», которое возглавлял сам царь Петр I, подписавший указ, в котором так была указана задача Шереметева: «Ради видения окрестных стран и государств и в них мореходных противу неприятелей Креста Святого военных поведений, которые обретаются во Италии даже до Рима и до Мальтийского острова, где пребывают славные в воинстве кавалеры». Борис Петрович был торжественно встречен и дважды принят Великим магистром Раймондом де Перейлосом. В знак уважения к России Великий магистр возложил на царского посла украшенные бриллиантами орденские знаки и, таким образом, Б. П. Шереметев стал первым русским православным почетным кавалером католического Ордена Св. Иоанна Иерусалимского.
И Борис Петрович Шереметев тоже будет рваться на борт военного судна госпитальеров, чтобы ввязаться в бой с иноверцами. В его подчинение будут переданы две боевые галеры, что, безусловно, показывает степень доверия русскому военачальнику.
Следом за ним рассчитывал лично побывать у рыцарей и Петр I.
