В 1963 году Людмила устроилась на работу в театр «Современник», один из самых популярных в стране, и там вскоре едва не обрела нового возлюбленного. На эту роль претендовал актер Игорь Кваша. Судя по мемуарам М. Козакова (он тоже тогда работал в «Современнике»), Кваша всерьез увлекся Гурченко, даже выбрал ее себе в партнерши в спектакле «Сирано». Во время гастролей театра в Саратове Игорь объявил друзьям, что собирается жениться на Людмиле, хотя на тот момент был уже несколько лет женат. Однако в результате Кваша так и остался со своей женой, а Гурченко вскоре вышла замуж за Александра Фадеева-младшего – сына писателя Александра Фадеева и актрисы МХАТа Ангелины Степановой. Он тоже был актером (окончил Школу-студию МХАТ), однако малоизвестным. Из Театра Советской Армии, где он служил, его выгнали после того, как он отказался задержаться на несколько лишних минут на репетиции. По словам близко знавшего его Александра Нилина: «Фадеев ни в малой степени не интересовался ни литературой, ни искусством. Достоинства, несомненно ему присущие, лежали совершенно в иной области. Однако самое удивительное, что проявил он себя в полном блеске именно в кругу артистов и прочих деятелей художественного мира.
Ареной ничего не стоящего ему самоутверждения оказался ресторан ВТО, и в 60-е годы, когда автора «Молодой гвардии» уже не было на свете, фамилия Фадеев практически ежедневно звучала, не перекрываемая громкостью других фамилий, находившихся в то время у всех на слуху…
Пока дети других знаменитостей доказывали, он – заказывал. И не одной выпивкой и закуской ограничивался его заказ, он заказывал как бы музыку жизни, взвихренной вокруг занимаемого им ресторанного столика… Я обожал бывать вместе с ним в ВТО. Для официанток он безоговорочно был клиентом номер один. Ни один человек в мире искусства не умел с такой широтой тратить деньги в ресторане, как Шура. Это вполне искупало его абсолютную неспособность их зарабатывать. Годам к тридцати он остался вовсе без средств к существованию. И больше в ВТО не ходил: на халяву он не пил никогда…»
Однако и брак с Фадеевым-младшим оказался для Гурченко недолгим. В середине 60-х они развелись, и Гурченко какое-то время жила с актером Театра киноактера Анатолием Веденкиным. А в конце 60-х судьба свела ее с популярным певцом Иосифом Кобзоном. По словам певца: «Тот период был для Людмилы достаточно тяжелым. Она пребывала в жуткой депрессии – ее популярность сильно упала. Но тем не менее Гурченко оставалась Гурченко. Она пробовалась в один театр, в другой. Со съемок возвращалась с истерикой. И каждая из них почему-то заканчивалась словами: «Это невозможно! Не успеешь заявить о своем желании сняться или сыграть роль, как тебе сразу же лезут под юбку и тащат в ресторан!» Она очень болезненно реагировала на такие вещи, они ее унижали. Вот в такой момент я и подставил ей плечо…»
Молодые жили в двухкомнатной квартире Гурченко, а свою жилплощадь на проспекте Мира Кобзон отдал родителям и сестре, переехавшим из Украины в Москву. В течение трех лет звездная чета состояла в гражданском браке, после чего решила узаконить свои отношения. Произошло это в январе 1969 года, во время их гастролей в Куйбышеве. Как гласит легенда, на это решение повлиял инцидент, который произошел в гостинице «Волга»: там Кобзона и Гурченко отказались прописывать в одном номере, мотивируя это тем, что у них нет штампа в паспорте. На директора гостиницы Якова Хазова не подействовали даже уговоры тогдашнего руководителя куйбышевской филармонии Александра Блюмина. Тогда Иосиф и принял решение немедленно зарегистрировать брак с Людмилой. Произошло это в стенах все той же филармонии. Свидетелем со стороны жениха выступил Блюмин, а вот у Гурченко свидетеля не было вовсе. Говорят, когда служащая ЗАГСа хотела сделать соответствующую пометку в паспорте невесты, в ее документе не обнаружилось двух листков с графой «семейное положение». По требованию сотрудницы невесте пришлось лезть в сумочку и доставать эти листки на свет.
Как ни странно, но штамп в паспорте так и не спас семью от развода: прошло чуть меньше года – и супруги разлетелись в разные стороны. Почему? Сама Гурченко говорит на этот счет более чем откровенно: «Если спускаешься к машине, которую тебе подарил муж, и видишь там уличную проститутку, – разве может идти речь о ревности? Это просто грязь. В браке с Кобзоном ничего хорошего не было. Он умел сделать мне больно. Начинал подтрунивать: «Что это все снимаются, а тебя никто не зовет?» После этого брака я осталась в полном недоумении, и мне открылись такие человеческие пропасти, с которыми я до того не сталкивалась, и больше никому не позволю это с собой проделать!..»
О том, какими сложными были взаимоотношения двух звезд, вспоминает очевидец – поэт-песенник Павел Леонидов: «Тот Старый Новый год у меня в тумане. Я напился, и меня забрала к себе домой Гурченко. Ее дочка Маша была у Люсиной матери, кажется. С нами поехали еще Сева Абдулов и Володя Высоцкий…