Подробности жизни Нелидовой в первое время пребывания ее при дворе мало известны, но несомненно, что лучшей образовательной школой для нее послужило путешествие за границу, которое совершила она в 1781–1782 годах в свите Павла Петровича и Марии Феодоровны, посетивших, под именем графа и графини Северных, Германию, Италию, Швейцарию и Францию. Лишь после возвращения великокняжеской четы из этого путешествия имя Екатерины Ивановны Нелидовой начинает часто встречаться в записках и письмах современников, имевших случай следить за жизнью великокняжеской четы: о ней стали говорить как о любимице Павла Петровича, или, что казалось тогда однозначащим, как о его любовнице.
Действительно, за это время Нелидова приобрела при дворе великого князя особое значение. Через шесть-семь лет после выпуска своего из института Нелидова сделалась серьезнее, опытнее, а положение великого князя значительно изменилось к худшему: Екатерина, устраняя сына от дел правления, относилась к нему подозрительно и удалила от него лучшего его друга, князя Александра Куракина, замешанного в дело Бибикова; в то же время скончался граф Никита Иванович Панин, воспитатель Павла, имевший огромное влияние на великокняжескую чету и в качестве опытного дипломата умело руководивший ее поведением в смысле, враждебном Екатерине. Лишившись людей, с которыми он издавна привык делиться мыслями и чувствами, Павел Петрович стал находить особое удовольствие в обществе Нелидовой, которая живостью своего ума, характером, искренностью и благородством своих суждений умела более других отвечать душевным его запросам. Любезный, рыцарский образ действий Павла придавал его вниманию к Нелидовой вид ухаживания, но первоначально этому не придавала никакого значения даже жена Павла, Мария Феодоровна, так как Нелидова была некрасива лицом.
Чувства Нелидовой к Павлу Петровичу проистекали, конечно, из чистого источника: положение Павла в царствование Екатерины, даже независимо от личных его свойств, несомненно, должно было вызывать сочувствие; притом лица, окружавшие великого князя, видели, как впечатлительная, пылкая, порывистая натура Павла под влиянием окружавших его тяжелых условий с каждым годом изменялась к худшему: горячность сменялась постепенно раздражительностью, доходившею до бешенства, осторожность – крайней подозрительностью; вечное недовольство своим положением выражалось в сумрачном, суровом настроении духа, в мысли, что ему не оказывают и не хотят оказывать должного его сану уважения, а боязнь, что он окружен шпионами и врагами, действующими по наущению Екатерины и ее фаворитов, сделала его доверчивым к сплетням и наговорам интриганов, желавших заслужить внимание великого князя и вкрасться в милость к нему. Оттого психическая природа Павла Петровича начала постепенно показывать признаки расстройства: мозг и нервы его были слишком утомлены от постоянного напряжения в одном направлении.