Их роман закончился в 1894 году в связи с помолвкой наследника. Уже давно велись переговоры о его свадьбе со многими европейскими домами. Из всех представленных ему потенциальных невест Николаю больше всего понравилась принцесса Гессен-Дармштадтская Алиса. Это была настоящая любовь с первого взгляда. Но поначалу родители Николая были категорически против этого союза – слишком незавидной казалась им невеста из захудалого немецкого дома, хоть и внучка самой королевы Виктории. Кроме того, сестра Алисы, принцесса Елизавета, уже была замужем за российским Великим князем Сергеем Александровичем, и новые родственные отношения были нежелательны. Кшесинская всячески поддерживала Николая в стремлении соединить свою жизнь с той, к кому его влечет, – впоследствии императрица, которой Николай рассказал о своем романе с Матильдой, была ей очень признательна за поддержку. Но большинство европейских принцесс отказывались переходить в православие – а это было необходимым условием для свадьбы. И в конце концов тяжелобольной Александр дал свое согласие на этот брак. О помолвке Алисы Гессенской и Николая Александровича было объявлено 7 апреля 1894 года.
20 октября 1894 года в Ливадии умер император Александр III – ему было всего 49 лет. На следующий день Алиса приняла православие и стала Великой княжной Александрой Федоровной. Через неделю после похорон императора Николай и Александра обвенчались в Зимнем дворце – для этого специально был прерван траур, наложенный при дворе на год.
Матильда очень переживала расставание с Николаем. Не желая, чтобы кто-нибудь видел ее страдания, она заперлась дома и почти не выходила. Из-за траура спектаклей в Мариинке практически не было, и Кшесинская приняла приглашение антрепренера Рауля Гюнцбурга уехать на гастроли в Монте-Карло. Она выступала вместе с братом Иосифом, Ольгой Преображенской, Альфредом Бекефи и Георгием Кякштом. Гастроли прошли с большим успехом. В апреле Матильда с отцом выступали в Варшаве. Здесь прекрасно помнили Феликса Кшесинского, и на выступлениях семейного дуэта публика буквально неистовствовала.
Но пора было возвращаться в Россию. Пока Кшесинская отсутствовала на сцене, там на место первой балерины, которое Матильда уже считала своим, стала претендовать приехавшая итальянка Пьерина Леньяни. Она практически сразу покорила петербургскую публику своей искрометной техникой. К тому же в связи с помолвкой и свадьбой Николая положение Кшесинской казалось далеко не таким прочным…
Тем не менее Матильда не осталась одна. Николай перед женитьбой поручил ее заботам своего друга и двоюродного брата, Великого князя Сергея Михайловича. Тот стал не только официальным «покровителем» Матильды на следующие несколько лет, но и ближайшим ее другом. Продолжали покровительствовать Кшесинской и старшие Великие князья, братья покойного императора, не меньше своего племянника очарованные этой маленькой балериной. Да и сам Николай продолжал следить за карьерой своей бывшей возлюбленной.
Коронационные торжества были назначены на май 1896 года. В программе значился парадный балет «Жемчужина» на сцене Большого театра. Для общих репетиций балетная труппа Мариинки должна была соединиться с труппой Большого театра. Балет ставил Петипа на музыку Риккардо Дриго, главные роли исполняли Леньяни и Павел Гердт. Выступление Кшесинской перед молодой императрицей сочли неуместным и никакой роли ей не дали. Оскорбленная Кшесинская бросилась к дяде императора, Великому князю Владимиру Александровичу, который всегда ей покровительствовал, и попросила его вступиться за нее. В результате дирекция получила личное распоряжение императора ввести Кшесинскую в балет. К этому времени все роли были уже распределены и срепетированы. Дриго пришлось сочинять дополнительную музыку, а Петипа поставить для Кшесинской па-де-де Желтой жемчужины (в балете уже были Белая, Черная и Розовая). Положение Кшесинской было восстановлено.
В ноябре 1895 года Кшесинская получила давно заслуженное звание балерины, которое присуждалось лишь лучшим танцовщицам труппы.
Но Кшесинская выдвинулась не только благодаря благосклонности царской фамилии. Она была действительно чрезвычайно талантливой танцовщицей, с огромным упорством работавшей над собой. Ее целью было стать первой балериной на российской сцене. Но тогда это представлялось практически невозможным: в русском балете безраздельно царили итальянские балерины.