Подробности жизни Нелидовой в первое время пребывания ее при дворе мало известны, но несомненно, что лучшей образовательной школой для нее послужило путешествие за границу, которое совершила она, в 1781–1782 г., в свите Павла Петровича и Марии Феодоровны, посетивших, под именем графа и графини Северных, Германию, Италию, Швейцарию и Францию. Лишь после возвращения великокняжеской четы из этого путешествия имя Екатерины Ивановны Нелидовой начинает часто встречаться в записках и письмах современников, имевших случай следить за жизнью великокняжеской четы: о ней стали говорить, как о любимице Павла Петровича, или, что казалось тогда однозначащим, как о его любовнице. Действительно, за это время Нелидова приобрела при дворе великого князя особое значение. Чрез шесть-семь лет после выпуска своего из института, Нелидова сделалась серьезнее, опытнее, а положение великого князя значительно изменилось к худшему: Екатерина, устраняя сына от дел правления, относилась к нему подозрительно и удалила от него лучшего его друга, князя Александра Куракина, замешанного в дело Бибикова; в то же время скончался граф Никита Иванович Панин, воспитатель Павла, имевший огромное влияние на великокняжескую чету и, с качестве опытного дипломата, умело руководивший ее поведением в смысле, враждебном Екатерине. Лишившись людей, с которыми он издавна привык делиться мыслями и чувствами, Павел Петрович стал находить особое удовольствие в обществе Нелидовой, которая живостью своего ума, характером, искренностью и благородством своих суждений умела более других отвечать душевным его запросам. Любезный, рыцарский образ действий Павла придавал его вниманию к Нелидовой вид ухаживания, но первоначально ему придавала никакого значения даже супруга Павла, Мария Феодоровна, так как Нелидова была некрасива лицом.
Чувства Нелидовой к Павлу Петровичу проистекали, конечно, из чистого источника: положение Павла в царствование Екатерины, даже независимо от личных его свойств, несомненно должно было вызывать сочувствие; при том лица, окружавшие великого князя, видели, как впечатлительная, пылкая, порывистая натура Павла, под влиянием окружавших его тяжелых условий, с каждым годом изменялась к худшему: горячность сменялась постепенно раздражительностью, доходившею до бешенства, осторожность - крайней подозрительностью; вечное недовольство своим положением выражалось в сумрачном, суровом настроении духа, в мысли, что ему не оказывают и не хотят оказывать должного сану его уважения, а боязнь, что он окружен шпионами и врагами, действующими по наущению Екатерины и ее фаворитов, сделала его доверчивым к сплетням и наговорам интриганов, желавших заслужить внимание великого князя и вкрасться в милость к нему. Оттого психическая природа Павла Петровича начала постепенно показывать признаки расстройства: мозг и нервы его были слишком утомлены от постоянного напряжения в одном направлении. Образ мыслей Павла, нравственный мир его оставались возвышенны, благородны, по-прежнему, но его действия, как плод расстроенного воображения и испортившегося характера, начинали уже смущать окружающих своею резкостью и непоследовательностью. Мало-помалу все друзья Павла стали, как будто сговорившись, смотреть на него, как на дорогого больного, нуждающегося в некотором присмотре и опеке. Цель у опекающих, при возможном единстве их интересов была одна - счастье Павла, и совместные действия опекающих, их, так сказать, дружеские заговоры, и увенчивались часто успехом, временно, в каждом отдельном случае. Но согласие друзей не могло продолжаться долго, так как вскоре выдвинулся вопрос о том, чье именно влияние на Павла должно было быть преимущественным; при том сам дорогой больной, почувствовав дружеские тиски и узнав о заботливом присмотре за собою, естественно захотел избавиться от непрошеных опекунов и показать себя самостоятельным. Тогда-то, вслед за разрушением дружеского союза, наступил удобный момент для действия разного рода интриганов, и стали вырастать в своем значении едва заметная сначала фигура главного из них, великокняжеского камердинера и брадобрея, Ивана Кутайсова.
Великая княгиня Мария Феодоровна в глубине души едва-ли могла быть довольна тем, что некоторое влияние на ее супруга имеет другая женщина, ее фрейлина. С другой стороны, Нелидова, естественно, увлекалась своею ролью друга Павла Петровича: ее самолюбию льстило влияние, приобретенное ею над его умом, и она не замечала, сколько затаенной горячи должно было накипать в душе Марии Феодоровны всякий раз, когда сила влияния Нелидовой как бы подчеркивала ее собственную слабость. Несомненно, что таких случаев было очень много в жизни великокняжеского двора, в особенности когда Павел Петрович уединялся на летнее и осеннее пребывание в Павловск и Гатчину. При всем том, Мария Феодоровна, вероятно, сумела бы скрыть свое огорчение по этому поводу и примениться к обстоятельствам, если бы возле нее не было подруги ее детства, г-жи Бенкендорф, которая, играя сначала главную роль при великокняжеском дворе, обнаруживала нерасположение к русским фрейлинам, и, конечно, не радовалась возвышению Нелидовой. Нелидова предчувствовала, что в будущем ей предстоит борьба с великой княгиней, и хотела заранее удалиться, зная хорошо, что успех будет не ее стороне; еще перед отправлением своим в Финляндию, надеясь участвовать в военных действиях, Павел прислал Нелидовой краткую, но многозначительную записочку на клочке бумаги: "знайте, что умирая я буду думать о вас". Но знаки внимания великого князя, его аффектация, проявлявшаяся на глазах у всех, также имела свою оскорбительную для Нелидовой сторону: уже с 1785 года при дворе и в обществе, по замечанию современника, "Нелидова была любовницей Павла".
Как бы ни были убеждены многие современники в справедливости этих слухов, но ложность их можно считать доказанною. Привязанность Павла к Нелидовой объясняется исключительно психологическими мотивами и той противоположностью, которая сказалась вполне определенно в это время в личностях Марии Феодоровны и ее фрейлины. Им обеим было около 30-ти лет. Великая княгиня была очень красива, высока ростом, белокура, склонна к полноте и близорука; обращение ее было крайне скромно, - до того, что она казалась слишком строгою и степенною (но мнению некоторых - скучною). Нелидова была маленькой брюнеткой, с темными волосами, блестящими черными глазами, с лицом некрасивым, но весьма выразительным; по свидетельству современников она танцевала с необыкновенным изяществом и живостью, а разговор ее, при совершенной скромности, отличался остроумием и блеском. По душевному своему настроению и складу своего ума, Мария Феодоровна постепенно расходилась с своим супругом все более и более, тогда как в беседе с Нелидовой Павел Петрович находил видимое себе удовлетворение. Бурный, мечтательный, отчасти мистический ум Павла, измученного в его трудном положении нравственной борьбой, искал средств согласить действительность с высшими идеальными воззрениями; вместе с тем, великий князь никогда не забывал, что он будущий русский самодержец, и даже военным своим занятиям, страсти своей к мелочам военного дела, придавал серьезный характер подготовки к будущим своим государственным обязанностям. Между тем, Мария Феодоровна, не умея владеть умом своего супруга и обуздывая порывы его раздражительности лишь кротостью и терпением, противопоставляла государственным заботам Павла - хлопоты пред императрицей о делах немецкой своей родни, его неудовлетворенным стремлениям к высшей правде - возможно спокойное, прозаическое отношение к жизни, способность мириться с обстоятельствами и даже применяться к ним. Всего менее Павел Петрович мог успокоиться на сентиментализме Марии Феодоровны, мало интересовался ее занятиями искусствами и хозяйством и вовсе не находил себе утешения в тех театральных зрелищах, литературных чтениях и невинных играх, которыми Мария Феодоровна наполняла свои досуги и думала развлекать своего сумрачного, скучавшего цесаревича. Дети, являющиеся обыкновенно связующим звеном между родителями, даже мало симпатизирующими друг другу, не могли играть этой роли в жизни великокняжеской четы: Екатерина забрала к себе своих внуков и внучек и давала им воспитание согласно собственным своим воззрениям, не считая нужным справляться о чувствах отца и матери. При всем том, Павел Петрович высоко ценил семейные добродетели Марии Феодоровны и относился к ней с уважением и благодарностью. Тем не менее, после Финляндского похода сделалось совершенно ясно, что умом Павла и сердцем его владела Нелидова. Ее отношения, юмор, живость, даже ее "bizarreries de caractère", вполне отвечали характеру Павла, который в обществе своей супруги находил наоборот размеренную немецкую аккуратность и методичность. Смелость, решительность действий молодой фрейлины, не боявшейся откровенно выражать свои мнения, внушали доверие к ее искренности, тогда как покорность Марии Феодоровны всегда казалась Павлу пассивным противодействием и имела вид молчаливого протеста. Набожность Павла была мечтательная и тесно связана с мистицизмом, и в этом отношении не мог он не ценить выспреннего, склонного к вере во все таинственное ума Нелидовой. Наконец самолюбию цесаревича льстила самоотверженная, бескорыстная преданность молодой девушки, идеализировать которую и платонически поклоняться ей было в рыцарских его видах. Зато Нелидова с чисто женским чутьем умела понять характер великого князя и хорошо владела его темпераментом, что не далось его супруге. В одном из позднейших своих писем к Павлу Петровичу и Марии Феодоровне, уже занимавшим в то время императорский трон, сама Нелидова, со свойственною ей искренностью, нарисовала одну из тех бытовых сцен, которые весьма часто, вероятно, происходили между царственными супругами.
"Каждый день, - пишет она, - меня радует хорошая погода мыслью, что моя добрая и дорогая императрица пользуется прогулкою, столь нужною для нее, и что император в лучшем расположении духа, ибо, не в гнев будь сказано его величеству, у меня есть маленькое подозрение, основанное на маленьких доказательствах, что погода действует на его физическое состояние, физическое на нравственное, оно же в свою очередь на нравственное состояние других, и т. д. и т. д., и вот добрые друзья спрашивают его голосом не совсем твердым: "что с вами, не рассердили ли вас чем-нибудь?" И вот он им отвечает, с видом и тоном глубокого убеждения: "ничего со мной не делается. Это вы в дурном расположении духа и стараетесь во всем мне перечить". И вот мы начинаем оправдываться, а над нами разражается гром словами: "О, если так, так я уеду куда-нибудь". Поэтому-то, когда я вижу хорошую погоду, мое воображение рисует мне сцены иного рода, на которых оно любит останавливаться и я вижу ту физиономию, которая так часто заставляет всех говорить: "у императора - прелестная физиономия, когда он спокоен". И вот тот пункт во всей истории, на котором я хочу остановиться".
Сама Нелидова иначе поступала с Павлом, даже после восшествия его на престол. "В характере Павла, - замечает Саблуков, - было истинное благородство и великодушие, и хотя он был ревнив к власти, но презирал те лица, которые слишком подчинялись его воле в ущерб истине и справедливости, а уважал тех, которые для того чтобы защитить невинного, бесстрашно противились вспышкам его гнева". Саблуков, бывший на карауле в Гатчинском дворце, был однажды свидетелем следующей сцены. Около самой офицерской караульной комнаты, - пишет он, - была обширная прихожая, в которой стоял караул, а из этой прихожей длинный, узкий коридор вел во внутренность дворца, и тут поставлен был часовой, чтобы вызывать караул каждый раз, как император шел оттуда. Вдруг я услышал крик часового: "на караул!" выбежал из моей комнаты, и едва солдаты успели схватить свои ружья, а я обнажить свою шпагу, как дверь коридора отворилась настежь, а император, в башмаках и шелковых чулках, при шляпе и шпаге, поспешно вошел в комнату, и в ту же минуту дамский башмак, с очень высоким каблуком, полетел чрез голову его величества, чуть-чуть ее не задевши. Император чрез мою комнату прошел в свой кабинет, а из коридора вышла Катерина Ивановна Нелидова, спокойно подняла свой башмак, надела его и вернулась туда же, откуда пришла. На следующий день, когда я снимал караул, его величество пришел и шепнул мне: "Mon cher, у нас вчера была ссора". - "Точно так, государь", - отвечал я. В это время (1797 г.) Нелидовой было уже 39 лет, но отношения ее к Павлу, очевидно, не изменились ни на йоту.
Конечно, весьма трудно, иногда даже невозможно, проникнуть в тайники человеческой души, недоступные даже самопознанию, но насколько можно думать, самолюбию и гордости Нелидовой должно было льстить влияние, приобретенное ею над Павлом Петровичем, и неудивительно, что постепенно она сама, в своей восторженности, пришла к убеждению что сам Бог предназначил ее охранять цесаревича и руководить им для общего блага. Сознание чистоты своих отношений к нему укрепляло Нелидову, среди шума возникших неблагоприятных о ней толков, продолжать свои сношения с Павлом. "Знаете ли вы, - писала она однажды Павлу, - почему вы любите ворчунью? это потому, что сердце ваше знает лучше, чем ваш ум, и что, несмотря на все предубеждения последнего, первое отдает ей справедливость". "Разве я когда-либо, - писала она Павлу незадолго до его кончины, смотрела на вас, как на мужчину? Клянусь вам, что я не замечала этого с того времени, как к вам привязана; мне кажется, что вы - моя сестра". Чисто нравственный, даже религиозный характер связи Павла с Нелидовой, имевший отчасти мистическую подкладку, неоднократно, засвидетельствован был самим Павлом, всегда искренним, всегда глубоко-религиозным. Посылая Нелидовой одну книгу духовного содержания, Павел писал ей: