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