В 1781 году Екатерина, надеясь убедить своего сына, симпатизировавшего Пруссии, в преимуществах ее новых дружеских отношений с Иосифом II Австрийским, организовала для Павла и Марии путешествие в Европу. Оно должно было продолжаться год, в течение которого супругам предстояло посетить Вену, Италию, родной дом Марии в Вюртемберге и Париж, однако Берлин был намеренно исключен. Мария Федоровна с нетерпением ждала возможности увидеть родных, но ее счастье было омрачено сообщением о том, что дети останутся дома. Разочарование Петра носило политический характер: отказ матери в повторном посещении Берлина означал, что он не сможет продолжить свое общение с Фридрихом. Напряженные отношения между матерью и сыном усилились после совпавшего с этим смещения Никиты Панина с лидирующего положения в иностранной коллегии. Отставка Панина была связана с отказом Екатерины в посещении Павлом Берлина. Близкие отношения между Россией и Пруссией, которые являлись центром международной политики Панина, стали распадаться по мере того, как укреплялась дружба между Екатериной и Иосифом II Австрийским. Иосиф посетил Екатерину в Санкт-Петербурге годом ранее, и императрица надеялась, что Австрия станет ее партнером и союзником против Турции.
1 октября 1781 года Павел и Мария отправились в путь. Пара путешествовала инкогнито как граф и графиня дю Нор. Мария, расстроенная разлукой с детьми, трижды падала в обморок прежде, чем экипаж смог сдвинуться с места. Однако в дороге она быстро пришла в себя, и путешествие стало настоящим триумфом. Екатерина проявила щедрость, предоставив триста тысяч рублей на расходы в путешествии. Она писала нежные письма «моим дражайшим детям», советовала им немедленно возвращаться домой, если у них появится тоска по родине, а также сообщала, что трехлетнему Александру «вручили карту Европы, чтобы он мог отслеживать маршрут, которым следовали его родители».
Их первой остановкой стала Польша, где Станислав оказался очарован Марией Федоровной. Екатерине было любопытно узнать про своего бывшего любовника, и она спросила Павла, «по-прежнему ли польский монарх остается приятным собеседником, или заботы о государстве лишили его этой особенности». Она добавила: «Мой старый друг может испытывать трудности, пытаясь отыскать сходство между моими нынешними портретами и лицом, которое он запомнил в прошлом».
Теплый прием в Польше стал предвестником следующих событий. Иосиф II подъехал к границе Австрии, чтобы поприветствовать наследника российского престола. Вена праздновала приезд супругов, а Мария наслаждалась элегантным австрийским двором. Визит, на который вначале отводилось две недели, продлился месяц, в течение этого времени Павел несколько охладел в отношении Пруссии и проникся симпатией к Иосифу II. Когда его гости отправились на юг, Иосиф сообщил своим родственникам в Тоскане и Неаполе, что великая княгиня «предпочитает тушеные фрукты изысканным десертам, и ни она, ни ее супруг не притрагивались к вину. Они очень любят минеральную воду».
Габсбургские принцы в Италии также оказали супругам теплый прием, но кульминацией долгого путешествия стал Париж. Толпы народа приветствовали молодую пару, где бы она ни появлялась: в театре, на ипподроме или на прогулке в садах Тюильри. В Версале Мария Антуанетта, сестра Иосифа II, постаралась угодить Павлу и писала: «Великий князь производит впечатление человека горячего и стремительного, но старающегося сдерживать себя». Королева обращалась с великой княгиней как со старой и близкой подругой. Подарила ей редкий фарфоровый обеденный сервиз, произведенный в Севре. Мария сначала решила, что он предназначался ее свекрови, императрице, пока не увидела на тарелках переплетенные гербы России и Вюртемберга.
Возвращение в Россию сопровождалось болезненной акклиматизацией. Граф и графиня дю Нор отсутствовали четырнадцать месяцев, при первой встрече с сыновьями мальчики смотрели на них как на чужих людей и цеплялись за бабушкину юбку. Казалось, императрица намеренно решила омрачить чувство удовлетворенности, оставшееся у супругов после поездки. За границей Павла встречали с распростертыми объятиями и делали все, чтобы он ощутил собственную значимость, теперь же Екатерина сказала ему, что путешествие испортило его. Молодую великую княгиню ждала другая, особая отповедь. Она сделала несколько заказов у шляпницы Марии Антуанетты, знаменитой мадемуазель Бертин. Коробки из Парижа все еще не были распакованы после приезда в Санкт-Петербург, когда Екатерина запретила носить при дворе высокие головные уборы с перьями, как раз такого фасона, которые привезла с собой Мария, желавшая подражать королеве Франции. Жене Павла велели вернуть покупки, ей было сказано, что высокой женщине больше идут простые русские наряды, а не безвкусная парижская мишура. Между тем Павел узнал, что здоровье Никиты Панина ухудшилось. В 1783 году великий князь и его жена оказались у смертного ложа человека, который был учителем, советником, защитником и другом Павла в течение двадцати трех лет.