Нездоровье повело к охлаждению отношений между нею и Александром, которому к этому времени было чуть больше сорока лет. Природа, как известно, не терпит пустоты, и сердечный вакуум был вскоре заполнен: по утверждению изучавшего «донжуанский список» Александра II историка Г. И. Чулкова, царь последовательно переменил полдюжины любовниц. Чулков называет Долгорукову 1-ю (не следует путать ее с Долгоруковой Екатериной Михайловной, о которой речь впереди), Замятнину, Лабунскую, Макову, Макарову и Ванду Кароцци. Сюда же вплетает Чулков мимолетную и совершенно скандальную историю с какой-то гимназисткой, дочерью камер-лакея. Однако все эти увлечения, если они и были, представляли собою не более чем слухи и сплетни, за исключением истории с двадцатилетней красавицей княжной Александрой Сергеевной Долгоруковой (Долгоруковой 1-й). Княжна обладала сильным характером и четким, мужским умом. Однако через непродолжительное время император охладел к ней. Дав ей понять, что возврат к прежним отношениям невозможен, Александр способствовал скорому замужеству Александры Сергеевны. Мужем бывшей фаворитки стал генерал Альбединский, вскоре после свадьбы отправленный генерал-губернатором в Варшаву.
Став мадам Альбединской, бывшая мадемуазель Долгорукова навсегда ушла из жизни императора, и он едва ли рассчитывал услышать когда-нибудь ее девичью фамилию.
Однако судьбе было угодно распорядиться иначе.
Весной 1865 года сорокасемилетний император прогуливался в Летнем саду. Он заметил прелестную девушку — грациозную, модно одетую, с румянцем во всю щеку, с большими лучистыми глазами. Это была дальняя родственница Александры Долгоруковой — теперь Альбединской — восемнадцатилетняя княжна Катенька Долгорукова.
Александр знал ее давно. Летом 1857 года, оказавшись на больших маневрах под Полтавой, он останавливался в имении ее отца — князя Михаила Михайловича Долгорукова и тогда-то впервые увидел Катеньку. Девочка поразила его ласковостью, непосредственностью и грацией, и царь запомнил ее. Через несколько лет Долгоруковы разорились — из-за непрактичности и широкого образа жизни. Их усадьба была несколько раз описана кредиторами, и, только продав фамильные бриллианты и золото, Долгоруковы смогли уплатить проценты и спасти Тепловку от публичных торгов с молотка. Подкосила их и реформа 1861 года, а еще более — неожиданный пожар, погубивший большой и богатый дом. После этого княгиня Вера Долгорукова написала Александру о всех постигших их несчастьях, и царь велел определить четверых мальчиков в петербургские кадетские корпуса, а Катеньку и Машеньку — в Смольный. Кроме того, Александр остановил «экзекуцию» банков и тем спас семью от окончательного разорения. Однако переживания последних лет настолько подорвали здоровье князя Долгорукова, что он вскоре умер, а его вдова переехала в Петербург и, сняв скромную маленькую квартирку, жила от воскресенья до воскресенья, когда к ней могли прибегать сыновья. Иногда навещала она дочерей, прилежно учившихся и мечтавших попасть при выпуске на мраморную доску первых в своих классах. Самой большой радостью для девочек были посещения матери и «царские дни», когда в Смольный приезжал царь и визит его сопровождался роскошным обедом и многочисленными подарками.
Александр приехал в Смольный в Вербное воскресенье 1865 года, и ему были представлены все преподаватели, наставницы и воспитанницы старших классов. Среди последних были и сестры Долгоруковы. Сестры Долгоруковы с самого начала оказались в числе наиболее красивых воспитанниц, хотя и непохожи друг на друга: Катенька была шатенкой с лицом цвета слоновой кости, Машенька — ярко выраженной блондинкой, с лилейным цветом кожи и привлекательной соразмерной полнотой. Увидев восемнадцатилетнюю Катю, Александр влюбился в нее, как бы это ни звучало банально, с первого взгляда. Александр доверил эту свою тайну фрейлине Вареньке Шебеко и стал посылать с нею сестрам Долгоруковым сладости и фрукты. Его выбор посредницы объяснялся тем, что Шебеко и раньше выполняла некоторые деликатные его поручения, и тем, что начальница Смольного института, мадам Леонтьева, была родственницей Шебеко. Леонтьева, конечно же, догадывалась о происходящем, но не только не препятствовала, но и всячески способствовала зарождению и развитию романа.
Вскоре после визита Александра Катенька простудилась, и ее положили в смольнинскую больницу, в маленькую отдельную палату. Шебеко провела царя к больной — Александр конечно же сохранял инкогнито, — и тогда визитер и больная впервые остались наедине. Как ни была Катя наивна, а все же догадалась, что она очень нравится императору.