На момент знакомства ей было 20 лет, ему 33. Наталья окончила литературное отделение МГУ и стала работать редактором в Госиздате, где и пересеклись их пути. Высокая, статная (ноги от ушей, сказали бы сейчас), поэту просто нельзя было пройти мимо. Они стали неразлучны, знакомым он представлял ее так: «Мой товарищ-девушка». Чтобы его Наталочка не опаздывала на свидания, Маяковский подарил ей часы. Вместе отдыхали в Ялте, где на день рождения В.В. преподнес ей огромный букет роз. Заявил: «Один букет – это мелочь. Мне хочется, чтоб вы вспоминали, как вам подарили не один букет, а один киоск роз и весь одеколон города Ялты!» И дальше осыпал подарками, ухаживал напропалую. Не знаем, доходило ли до прятания «своего звона в мягкое, женское» – со свечкой тут никто не стоял.

«Товарищ-девушка» хотела понять: ну а дальше-то что? В 1928 году произошло объяснение. Маяковский заявил Наталье Брюханенко, что у него только одна муза: «Я люблю Лилю. Ко всем остальным я могу относиться только хорошо или ОЧЕНЬ хорошо, но любить я уже могу только на втором месте. Хотите – буду вас любить на втором месте?»

Наталью такая конфигурация решительно не устраивала, роман закончился. Но они продолжали часто встречаться, дружить. За четыре дня до ухода Маяковского из жизни Брюханенко была у него в квартире в Гендриковом переулке, помогала править рукописи.