После замужества старшей сестры — великая княжна Мария Николаевна в 1839 году вышла замуж за герцога Лейхтенбергского, который, получив чин генерал-адъютанта и титул императорского высочества, переехал на постоянное жительство в Россию, — Ольга неизменно находилась при матери. Но мысль, что вряд ли ей, как старшей сестре, удастся остаться в родном гнезде, постоянно тревожила красивую головку великой княжны.
Вместе с матерью-императрицей Ольга в 1840 году посетила Веймар, где проживала великая княгиня Мария Павловна. О своей тете она в своих воспоминаниях написала много приятных слов. «
Между тем отца-императора начал беспокоить вопрос о браке его второй дочери. Правда, мысль о том, что, подыскав в европейских владетельных домах подходящую кандидатуру, ему придется с ней расстаться, очень огорчала его. Великая княжна Ольга, красивая, знающая несколько иностранных языков, увлекающаяся игрой на пианино и живописью, считалась одной из лучших невест в Европе. После старшей дочери, которая вышла замуж за принца ниже ее по рангу, Ольге августейшие родители хотели найти более перспективного супруга.
Но время шло, а таковой не определялся. При дворе недоумевали: «Как, в девятнадцать лет все еще не замужем?» И это при том, что претенденты на руку красавицы уже объявлялись.
Еще в 1838 году в Берлине, где шестнадцатилетняя великая княжна Ольга была вместе с родителями, она привлекла внимание наследного принца Максимилиана Баварского. Но он ни ей, ни родным не понравился.
Год спустя император стал прочить дочь-невесту в жены австрийскому эрцгерцогу Стефану, решив — по политическим соображениям — восстановить родственный союз с габсбургским Домом, так трагично прервавшийся в 1801 году. Молодой эрцгерцог был старшим сыном венгерского палатина Иосифа, первым браком женатого на старшей сестре Николая I, скончавшейся при родах. Эта кандидатура в мужья Ольги была выбрана неслучайно. Еще в 1839 году старший сын российского императора, наследник престола Александр, путешествуя по Европе, подружился с эрцгерцогом во время визита в Вену. Молодой Стефан заметно выделялся своими способностями, что, как полагали, предвещало ему блестящее будущее. Славянин по духу, он любил Венгрию и свободно говорил по-венгерски, что отличало его от других придворных венского двора. В Будапеште в нем видели наследника его отца-палатина.
Вопрос о браке дочери российского императора с эрцгерцогом Стефаном активно обсуждался. Но габсбург-лотарингский Дом под различными предлогами свой ответ откладывал.
Между тем неожиданно пришло предложение руки и сердца от другого эрцгерцога — Альбрехта, двоюродного брата Стефана, не столь привлекательного и значительно его старше. Принц Альбрехт видел великую княжну Ольгу в Петербурге, который посетил в 1839 году. Тогда-то он и пленился красотой дочери императора. Пользуясь ситуацией — о браке кузена еще не было принято окончательного решения, — он направил письмо Николаю I, в котором просил руки великой княжны.
Как же отнеслась Ольга к этому предложению? Об этом она написала в своих «Воспоминаниях»:
«
Наконец пришел долгожданный ответ из Вены. В письме говорилось, что «
Таким образом, венский двор не пожелал, чтобы в стране, а тем более в Будапеште, появилась русская великая княжна, опасаясь вновь иметь палатину православной веры. Новый союз с австрийскими Габсбургами, в котором Россия видела большую будущность, не состоялся.