Он был тогда уже женат, что составляло противное статутам, однако в это время он не был женат по смерти супруги своей. Папа Иннокентий XII предложил его в кавалеры и дал свое разрешение. В сие время отходил большой караван мальтийских кавалеров, назначенный в Морею, при сем случае отправился и новый мальтийский кавалер 9 мая, и ночью выпровожен до сицилийских берегов.
10 февраля 1699 г. прибыл боярин в Москву и в немецком платье по возвращении предстал Петру Великому, по его повелению, и притом украшенный полученным на Мальте орденом. Монарх принял его весьма милостиво, поздравил кавалером, приказал ему орденский крест всегда носить и 19 февраля повелел в Разряде и во всех присутственных местах записать: "что титло его сверх боярского достоинства еще получено приращение, и как в Боярской книге, в Росписях и других бумагах, так и сам бы он писал: боярин и военный свидетельствованный мальтийский кавалер". Слово "свидетельствованный" доказывает сколько похвальных казалось в очах Монарха признание храбрости и заслуг боярина его от мальтийских кавалеров, а не сам он хвастает свидетельством иностранным".
Путешествие на Мальту стольника Толстого
В 1698 г. Мальту посетил боярин П.А. Толстой. В проезжей грамоте, выданной боярину 30 января 1697 г., было сказано: "По нашему Царского Величества указу послан в европейские христианские государства и княжества и в вольные городы дворянин Наш, урожденный Петр Андреев для науки воинских дел" [69].
П.А. Толстой посетил Польшу, германские земли, Венецию и прибыл на Мальту 19 июля 1698 г., через два месяца после Б.П. Шереметева. Боярина принял Великий Магистр, разрешивший ему ознакомиться с оснасткой орденских военных кораблей и укреплениями Мальты.
При отъезде с острова П.А. Толстой получил свидетельство о пребывании на Мальте и личном участии в морском сражении с турками, и через Неаполь, Рим, Флоренцию и Венецию вернулся в Москву.
Историк Н. Попов писал в своей работе "Путешествие в Италию и на остров Мальту стольника П.А. Толстого в 1697 и 1698 гг.":
"Задумав обширный план собственного путешествия по Европе, Петр Великий кроме людей, вошедших в состав посольства, отправил еще около 60 человек в Англию, Голландию и Италию, преимущественно для изучения морского дела.
Покидая Неаполь Толстой пустился в наемной фелюге к Мальте, которой достиг 19 июля 1698 г.
Гроссмейстер принял его радушно; сняв шляпу и поклонившись, говорил он Толстому: "Я де себе почитаю за великое счастье, что де ты, великого государя человек, из дальних краев приехал видеть охотою мое малое владетельство, Мальтийский остров". Отблагодарив за ласковый прием, Толстой просил у гроссмейстера по вольности осмотреть Мальту; гроссмейстер предложил ему для того свою карету, а кавалера Полявичино в руководители. Осмотрев соборную церковь святого Иоанна Предтечи, Толстой и его спутник вернулись в австерию, "для того, что час того времени был жарок, и мало позабавились лимонатами. Между тем гроссмейстер присылал своего покоевого человека спросить Толстого о здоровье и не имеет ли он каких нужд" [67].