Лейла Алиева работала машинисткой в бюро Всемирной организации здравоохранения в Копенгагене. Лейла была полукровка (мать русская, отец азербайджанец), высокая и стройная, с яркой внешностью, с копной темных волос, глубоко посаженными глазами и длинными ресницами. В отличие от Елены, она была застенчивой и несветской, но когда переставала стесняться, смеялась громко и заразительно. Ей нравилось петь. Как и Олег, Лейла родилась в кагэбэшной семье: ее отец, Али, дослужился до звания генерал-майора в рядах КГБ Азербайджанской ССР, а выйдя в отставку, перебрался в Москву. Лейла воспитывалась в строгих мусульманских традициях и детство провела почти в изоляции. Ее немногочисленных кавалеров родители подвергали строжайшим проверкам. Работать она начала машинисткой в конструкторском бюро, затем занималась журналистикой в комсомольской газете, а потом через Министерство здравоохранения подала заявку на секретарское место при европейском отделении ВОЗ. Как и всех советских граждан, желавших работать на какую-либо иностранную организацию за рубежом, Лейлу самым тщательным образом проверили на идейную надежность и лишь потом разрешили ей поехать в Копенгаген. Ей было двадцать восемь лет, она была на одиннадцать лет младше Олега. Вскоре после приезда в Данию Лейлу пригласили на прием, который устраивала жена посла, и та поинтересовалась, чем Лейла занималась в Москве.
— Я была журналисткой, — ответила девушка. — И мне хотелось бы написать что-нибудь о Дании.
— Тогда нужно познакомить вас с пресс-атташе в посольстве, товарищем Гордиевским.
Так Олег Гордиевский и Лейла Алиева принялись сообща работать над статьей для комсомольского журнала, посвященной трущобному району Копенгагена. Статью эту потом так и не напечатали. Но очень скоро их сотрудничество переросло в нечто иное. «Общительная, умная, обаятельная, со своеобразной внешностью, она отличалась к тому же и прирожденным остроумием, и страстным желанием нравиться окружающим. Я влюбился в нее с первого взгляда, и наша любовь, вспыхнув, словно молния, озарила нашу жизнь». Освободившись от неусыпного родительского надзора, Лейла самозабвенно закрутила роман с женатым мужчиной.
«Поначалу он казался мне таким серым, — вспоминала Лейла. — Повстречав его на улице, вы бы его просто не заметили. Но когда мы начали разговаривать, я была поражена. Он столько всего знал! Он оказался таким интересным человеком, с прекрасным чувством юмора. Потихоньку я в него влюбилась».
Природная незлобивость и мягкая простота Лейлы — после спесивой склочности Елены — стали для Гордиевского настоящим бальзамом на душу. Сам он привык все просчитывать в человеческих отношениях, постоянно оценивал и собственные, и чужие поступки и слова. Лейла же была простодушна, отзывчива и раскованна: Олег впервые в жизни почувствовал, что его обожают. Гордиевский принялся знакомить свою молодую возлюбленную с новыми для нее произведениями литературы, раскрывавшими мир идей и вещей, запрещенных в СССР. По его настоянию она прочла «Архипелаг ГУЛАГ» и «В круге первом» Александра Солженицына, где описывались мрачные зверства сталинизма. «Он давал мне книги из своей библиотеки. Я приняла его близко к сердцу, этот водопад правды. Он просветил меня». Лейла с самого начала поняла — без чьих-либо подсказок, — что Гордиевский служит в КГБ. Однако мысль о том, что интерес к подобным книгам может указывать на скрытое диссидентство, никогда не приходила ей в голову. На тайных свиданиях они строили грандиозные планы. Они решили, что обязательно заведут детей. В КГБ с неодобрением относились к супружеским изменам сотрудников, а к разводам и того хуже. «Мы встречались в глубочайшей тайне. Любое фото, которое свидетельствовало бы о связи на стороне, могли использовать против него, и тогда последовало бы очень серьезное наказание. Его могли выслать из страны в 24 часа». Им нужно было набраться терпения. Впрочем, Олегу было не привыкать к медленным и тайным ухаживаниям.
Гордиевский не покладая рук трудился на обеих своих работах. Еще он много играл в бадминтон. Лейла снимала квартиру вместе с другими двумя девушками, а Елена часто бывала дома, так что уединяться им с Лейлой приходилось крайне редко и с соблюдением множества секретных предосторожностей. Но здесь обман (с сопутствующей ему тревогой) возводился уже на новую ступень: Гордиевский изменял Елене вдвойне — на профессиональном и на личном уровнях. Разоблачение на любом из них грозило катастрофой. Маскировать следы двойной измены приходилось тщательно и осторожно. Раз в несколько дней он посылал Лейле шифрованное сообщение — и (каждый раз в разных копенгагенских гостиницах) изменял жене. Раз в месяц он отправлялся в ничем не примечательную квартиру в скучном датском пригороде — и там изменял родине. За год он выработал систему уверток, усыплявших бдительность советской разведки и подозрительность жены. Его тайные связи — и с Лейлой, и с МИ-6 — становились все глубже. Олег чувствовал себя в безопасности. Только здесь он ошибался.