У Галины Леонидовны было три официальных мужа, первые два — артисты цирка: акробат-силач Евгений Милаев (в 1952–1962 годах) и иллюзионист Игорь Кио. У некоторых женщин возрастная амплитуда их мужей похожа на нестабильную кардиограмму: первый муж Брежневой был старше ее на 19 лет, а второй — моложе на 15. С первым супругом она — студентка Кишиневского университета — познакомилась в 1951 году, когда в столицу Молдавии (партийным лидером которой был ее отец) приехал на гастроли цирк шапито. Ее покорил мужественный силач, подбрасывавший трехпудовые гири как груши — вдовец с двумя детьми. С ним она и уехала, бросив учебу. Какой поступок! Убежать с цирком шапито — на это способны только богемные натуры. Тут, конечно, возникает вопрос — а куда смотрела комсомольская организация университета, должная следить за морально-политическим обликом своих студентов? В том-то и дело, что Галина никак не хотела вступать в комсомол, на чем неоднократно настаивал отец. Он даже ее подруг просил повлиять на дочь.

В браке с Милаевым у Галины родилась дочь Виктория. «Милаев, — сообщает подруга Брежневой, — Галю боготворил, буквально носил ее на руках, делал шикарные подарки, осыпал бриллиантами, подарил соболью шубу. И она этого заслуживала. Галя была прекрасной женой, хозяйкой, великолепно готовила. Более того, приняла детей Милаева, Сашу и Наташу».

Галина Леонидовна любила кочевую жизнь, свойственную артистам цирка, к тому же она давала возможность выезжать за границу, что было огромным стимулом для нее. Позднее Игорь Кио рассказывал: «В тот год цирк отправился в Японию на гастроли. Галина охотно поехала туда вместе с Милаевым. То ли восточная экзотика так на нас повлияла, то ли Галине уже надоел ее муж, только неожиданно мы страстно друг в друга влюбились. Она и впрямь была необыкновенной: обольстительная, уверенная в себе, красивая, ухоженная, несколько манерная. Она немедленно сообщила мужу, что хочет развода».

Брак с восемнадцатилетним Кио в 1962 году продлился не больше двух недель: узнавший об очередном фокусе дочери Леонид Ильич приказал развести молодоженов, у которых отобрали паспорта, чтобы вырвать страницу с отметкой о браке. На паспорте Кио поставили отметку «Подлежит обмену». Но тайно встречаться влюбленные продолжали еще несколько лет, несмотря на зоркое око приглядывавших за ними сотрудников «наружки». Естественно, что Леониду Ильичу об этом докладывали лично. Но и советские люди жили не в безвоздушном пространстве, то тут, то там судачили в очередях о похождениях Галины.