В своих мемуарах Кшесинская вспоминает о появлении Александра III, который, возвышаясь над всеми, громко спросил: "Где Кшесинская?" Когда ему представили девочку, царь, взяв ее за руку, приветливо произнес: "Будь славой и украшением нашего балета". Во время ужина рядом с Матильдой сидел государь император. Потом он передвинулся, и его место занял цесаревич. Когда Кшесинская взглянула на Николая, "в сердцах каждого из нас возникло непреоборимое влечение друг к другу". Запись Николая в своем дневнике была более лаконичной: "Поехали на спектакль в театральное училище. Была небольшая пьеса и балет, - очень хорошо. Ужинали с воспитанниками".
С того момента Кшесинская норовила попасться на глаза Николая. Узнав, что цесаревич с сестрой Ксенией часто выходят на балкон Аничкова дворца, чтобы поглядеть на людей, прогуливающихся по Невскому проспекту, Кшесинская каждый день проходила мимо. В мае, в день тезоименитства наследника цесаревича, она украсила свою комнату бело-сине-красными флажками. В то лето ее назначили в труппу, которая выступала в деревянном театре для офицеров, расквартированных в Красном Селе, где цесаревич нес службу со своими гвардейцами. Он ежедневно приходил посмотреть выступления Кшесинской. Однажды, увидев их обоих беседующими, царь с улыбкой заметил: "Да вы, я вижу, флиртуете".
Поскольку цесаревич и балерина никогда не оставались наедине, дальше флирта в то лето у них не зашло. "Мне казалось, что, хотя он и не влюблен в меня, то питает ко мне известное расположение, и я предалась мечтам", писала она. "Положительно, Кшесинская 2-я меня занимает", - признавался в дневнике Николай. Несколько дней спустя он писал: "Разговаривал с маленькой Кшесинской через окно". Перед отъездом из лагерей он добавил: "После закуски в последний раз поехал в милый Красносельский театр. Простился с Кшесинской".
Николай Александрович не видел Матильду почти год. В октябре 1890 г. вместе с братом Георгием он отправился в девятимесячное плавание по Средиземному морю, через Суэцкий канал в Индию и Японию. Родители надеялись, что, проведя несколько месяцев на борту судна, согревшись под лучами солнца и надышавшись соленым морским воздухом, Георгий подлечит больные легкие. Для Николая же, наследника российского престола, рассчитывали августейшие родители, это путешествие явится важным событием, во время которого он обучится дипломатическим тонкостям и успеет позабыть молодых дам, которые начали осложнять его жизнь.
Кшесинская не была единственной из них. Николай Александрович нашел, что балерина привлекательна. Она была всегда под рукой, хороша собой, изыскивала всяческие способы дать ему понять, как он ей нравится. Но чувство, которое Николай питал к высокой золотоволосой принцессе Алисе Гессен-Дармштадской, оказалось гораздо глубже. Принцесса Алиса была младшей сестрой великой княгини Елизаветы Федоровны, двадцатипятилетней супруги великого князя Сергея Александровича, дяди наследника цесаревича. Елизавета Федоровна, которую близкие звали Эллой, была жизнерадостной женщиной, своими праздниками на катке и домашними театральными постановками вносившая юный задор в жизнь императорской семьи. Наследник часто гостил у молоденькой тетушки. Когда к старшей сестре Элле приехала двенадцатилетняя Алиса, визиты наследника участились. Внешне серьезная и робкая, Алиса была страстной по натуре. Впервые обратив взор своих серо-голубых глаз на Николая (ему было тогда шестнадцать), она тотчас почувствовала к нему симпатию. К сожалению, жила она далеко, в Гессен-Дармштадте. К тому же, родители цесаревича считали, что захудалая немецкая принцесса не подходящая партия для наследника российского престола.
С унынием в душе покинув С.-Петербург, Николай Александрович и Георгий Александрович отправились в Афины, где великих князей встретил их двоюродный брат, греческий принц Георгий. Там три кузена, сопровождаемые молодыми русскими аристократами, в том числе князьями Баратянским, Оболенским и Ухтомским, сели на борт русского фрегата "Память Азова". К тому времени, как фрегат достиг берегов Египта, путешественники подружились, и настроение у Николая значительно улучшилось. Сев на яхту египетского хедива, они совершили плавание вверх по Нилу. Изнемогая от жары, цесаревич разглядывал однообразные селения да кущи пальм, выстроившиеся вдоль берега. Останавливаясь в прибрежных городах, молодые аристократы заинтересовались искусством местных танцовщиц. "Ничего особенного", - записал наследник после первого представления. Но на следующий вечер появилась такая запись: "Этот раз было лучше. Они разделись и выделывали всякие штуки". Путешественники поднимались на две пирамиды, ели, как арабы, руками, катались на верблюдах. Яхта поднялась до Ассуанских порогов. Цесаревич наблюдал, как в бурной, пенящейся воде купались египетские мальчишки.