Точно неизвестно, завоевал ли молодой лорд сердце красивой арестантки еще в тюрьме или это произошло позже. Вышел он из заключения пятью годами раньше Елизаветы, по ходатайству Филиппа II Испанского, женатого на Марии, сводной сестре будущей королевы. Мария исполняла все желания супруга: она жестко преследовала протестантов, ввела инквизицию в Англии и подписала более 500 смертных приговоров в течение своего непродолжительного «кровавого» правления. Марии, однако, не удалось удержать своего мужа-испанца. Он покинул ее и вернулся на родину.
Роберт Дадли удостоился полного прощения с возвращением всех прав и с производством в фельдцейхмейстеры. Он тайно навещал Елизавету в Вудстоке, где она жила, всеми забытая: парламент, в угоду Марии Тюдор, объявил брак Генриха VIII с Анной Болейн недействительным, а Елизавету – незаконнорожденной, тем самым лишив ее надежд взойти на престол. Мария Тюдор сама мечтала иметь законных наследников от своего супруга Филиппа II. Последний, явно сочувствуя Елизавете, уговорил Марию позволить ей переселиться из Вудстока в более удобное место. Мария согласилась, и Елизавета перебралась в уединенный замок Гетфилд, где прилежно занималась науками, изучением языков и в свободное время – садоводством. Она продолжала встречаться с Дадли, который, чтобы избежать кривотолков, заботясь о репутации будущей своей королевы, женился на знатной, богатой девице Эми Робсарт, чьей памяти Вальтер Скотт посвятил так много трогательных страниц в своем романе.
Когда Мария Тюдор 17 ноября 1558 года умерла от водянки, так и не родив наследника престола, Елизавета стала королевой и неограниченной властительницей Великобритании. Тотчас же ее окружила толпа восторженных поклонников, среди которых был и Филипп II Испанский, ухаживавший за ней еще раньше. Елизавета ненавидела его как фанатичного католика, но ничем не выдавала своих чувств, а когда взошла на престол, решительно заявила, что намерена остаться королевой-девственницей. «Для славы Божьей, для блага государства я решила нерушимо хранить обет девственности. Взгляните на мой государственный перстень, – говорила она, показывая депутатам парламента на этот символ власти, еще не снятый после коронования, – им я уже обручилась с супругом, которому неизменно буду верна до могилы… Мой супруг – Англия, дети – мои подданные… Я изберу себе в супруги человека достойнейшего, но до тех пор желаю, чтобы на моей гробнице начертали "Жила и умерла королевою и девственницей"».
Обещание Елизаветы выбрать в супруги достойнейшего из достойных казалось Роберту Дадли намеком на его персону. Но в это время у Елизаветы не было отбоя от женихов. В первые недели правления Елизаветы граф Арундел взял взаймы у итальянского купца крупную сумму денег, которые щедро тратил на развлечения и подкуп подруг и слуг королевы, чтобы они склонили ее выйти замуж. Ее согласия домогались электорпалатин Казимир, эрцгерцог австрийский Карл, герцог Голштинский, наследный принц Эрик XIV Шведский. Посланник шведа при английском дворе, Гилленстиерн, узнав о нежных отношениях между Елизаветой и Дадли, уведомил Эрика об истинной причине упорства королевы и получил от него в ответ приказ нанять итальянца или француза и предложить ему 10 тысяч талеров за убийство фаворита.
Впрочем, самым скандальным из всех оказалось дело самого Роберта Дадли, графа Лестера, из-за которого политическая стабильность Англии оказалась под угрозой. Либо королева перешла все границы любовного флирта, либо она серьезно намеревалась выйти замуж за Роберта Дадли, но в течение нескольких месяцев пришлось удерживать ее от этого шага.
В августе и сентябре 1560 года, когда жена Дадли умирала от рака груди, Елизавета и Дадли строили планы о браке. Государственный секретарь Вильям Сесил заявил, что оставит свою должность в случае, если они поженятся, но одновременно начал борьбу против осуществления планов любовников. Он распространил слух, что Эми Дадли вовсе не больна – Елизавета и Дадли намерены отравить ее. Эту историю он рассказал даже испанскому посланнику и добавил, что Дадли несет гибель королевству. Эми умерла в сентябре, и на Роберта пали подозрения в ее убийстве. Случившееся вызвало шквал возмущений как при дворе, так и в стране, и на какое-то время замужество стало невозможным по политическим причинам.
Впрочем, Елизавета скоро успокоила фаворита. Она пожаловала красавца-лорда, прозванного сердцем двора, в обер-шталмейстеры королевы, в кавалеры ордена Подвязки с передачей замков и трех поместий. Затем пожаловала ему титул барона Денби и графа Лестера.
В 1572 году граф Лестер тайно обвенчался с леди Дуглас Говард, вдовой барона Шеффилда. Когда Елизавета узнала об этом, она хотела учинить расправу над неблагодарным лордом Лестером, но тот быстро развелся с женой и выдал ее за Эдуарда Стаффорда. От этого брака у него был сын Роберт Дадли, который тщетно ходатайствовал о признании законности своего рождения.