Екатерина Нелидова происходила из небогатой дворянской семьи Смоленской губернии и в шестилетнем возрасте была отдана на воспитание и обучение в только что организованный Институт благородных девиц в Петербурге. Институт, который чаще называли «Смольным» — по названию расположенного рядом Смольного женского монастыря, основан был в 1765 году Екатериной II по образу Сен-Сирского института мадам де Ментенон (фаворитки, а затем жены Людовика XIV, 1635–1719). Он предназначался для представительниц русских дворянских фамилий. Курс был рассчитан на Двенадцать лет, причём родители при определении в Институт давали подписку, что не заберут воспитанниц до окончания срока.

Начальницей Института Императрица определила «русскую француженку» Софью Ивановну Делафон (де Лафон, 1717–1797). Почти за двадцать лет то того овдовевшая гугенотка-протестантка де Лафон с двумя детьми на руках бежала из католической Франции и после многих мытарств и лишений обрела свой второй дом в России. Здесь она стала статс-дамой, получила крест ордена Святой Екатерины.

Институт должен был готовить «благопристойных барышень», способных бегло говорить по-французски, вести непринуждённую светскую беседу и стать по-европейски образованной женой и матерью. Воспитанниц учили иностранным языкам, русскому письму и чтению, в самой общей форме — арифметике, истории, географии, физике, а также рисованию, рукоделию, музыке, танцам.

К четырнадцати годам смолянки считались уже взрослыми девушками. В это время по воскресным и праздничным дням им дозволялось устраивать спектакли и концерты, на которые приглашались «дамы» и «кавалеры» по строгому выбору, с которыми институтки могли совершенствовать свое мастерство светского общения. Иногда давались балы, на которые приглашались кадеты из Шляхетского корпуса.

Екатерина Ивановна закончила Институт в первом выпуске в 1776 году, причём она вызвала симпатию Екатерины II своим умом, изяществом манер и природной грацией. Она назвала Нелидову «феноменом», подарила на выпускном акте бриллиантовый перстень и приказала художнику Дмитрию Левицкому (1735–1822) написать с неё портрет, где она изображена танцующей менуэт. Этот портрет так и остался единственным изображением Нелидовой…

Екатерина Ивановна сразу же в 1776 году была определена фрейлиной к первой супруге Цесаревича Великой княгине Наталье Ллексеевне. После смерти Натальи и женитьбе Павла Петровича на Марии Фёдоровне Нелидова стала и её фрейлиной. Павел Петрович не питал расположения к фрейлинам. Он считал их пустыми созданиями, занятыми только туалетами и сплетнями. К тому же все они назначались матерью, а значит — её наушницы. Мария Фёдоровна приняла этот взгляд, и первые годы держала фрейлин на известном расстоянии. Сближение началось во время заграничной поездки Великокняжеской четы, в которой, среди прочих, их сопровождала и Нелидова.

Именно там Павел Петрович сделал приятное открытие: оказывается, и среди фрейлин встречаются интересные особы, интересные не в смысле внешней привлекательности, тут Екатерина Ивановна уступала чуть ли не всем прочим, а в смысле душевных и умственных качеств. Она была содержательным человеком, умевшим не только чётко сформулировать вопрос и дать вразумительный, логический ответ, но и остроумно оценивать людей и события. К тому же она всегда в разговоре смотрела прямо в глаза, что свидетельствовало о прямоте и честности.