Пара познакомилась в стенах издательского дома Hearst Shkulev Media. На страницах журнала “СтарХит” Малахов рассказывал, что обычно он брал обед с собой, а в тот судьбоносный день отправился в столовую, где и встретил Шкулеву. Наталья не скрывает, что это был классический служебный роман. Однако первое свидание по-настоящему удивило Шкулеву — оно началось с ужина в вагоне поезда, а закончилось в довольно необычном для рандеву месте.

“Он звонит мне и говорит: “Ты поедешь со мной?” Я спрашиваю: “Куда?” — “Это сюрприз. Встречаемся через час на Павелецком”. Приезжаю, как договорились, на вокзал, а там меня уже ждет Андрей с цветами. Свидание было поздней весной, на мне был жакет Chanel, красивые брюки, на ногах — балетки. Мы заходим в СВ, а в нашем купе горят свечи Jo Malone и накрыт “стол” с французским вином и сырами. Куда едет этот поезд, я по-прежнему не знала. Мы разговаривали всю ночь напролет! Так началось наше первое свидание. А дальше мы, действительно, оказались в Брянске, в мужской колонии строгого режима, где Андрей снимал телевизионный сюжет”, — делилась воспоминаниями Наталья.

Четвертого октября 2010 года телеведущий сделал предложение руки и сердца избраннице. Для этого он выбрал один из самых модных ресторанов Нью-Йорка. Шкулева рассказывала, что Малахов встал на колено и преподнес кольцо. Этот поступок любимого человека растрогал Наталью до слез. После того, как она приняла предложение, все гости и официанты аплодировали паре. “А дальше началось невообразимое — мы все начали танцевать на столах, и шампанское лилось рекой”, — рассказывала бренд-директор журнала ELLE.

Влюбленные зарегистрировали брак четвертого июня 2011 года. В тот день они не стали устраивать пышное торжество, а обошлись скромным семейным ужином. Большой праздник новоиспеченный муж и жена устроили чуть позже — 13 числа в Версале. Супруги обожают путешествовать по всему миру, а потому решили провести церемонию в одном из самых красивых мест на земле — дворце во Франции. На торжестве присутствовали только родственники, а также самые близкие друзья и коллеги пары. Наталья выглядела безупречно в белом свадебном платье.

Главный редактор “СтарХита” обожает супругу — он не скрывает, что она изменила его жизнь.

“Я просыпаюсь рано утром и смотрю, как она спит. Мое лицо расплывается в улыбке, и я нежно глажу ее волосы, которые за три дня на море уже успели выгореть на солнце. Мне нравится в ней все: доброта, вкус, ее умение слышать и слушать, нежность и независимость”, — рассказывал Малахов.

Несмотря на то, что пара души не чает друг в друге, Наталье все же приходится мириться с недостатками супруга. “Андрей непунктуальный человек. Я борюсь с этим, но понимаю, что все бесполезно. Опоздать, как минимум, на полчаса — для него это обычное дело”, — признавалась Шкулева.

В начале августа этого года стало известно о том, что супруги ждут первенца. Об этом Малахов сообщил на страницах журнала “СтарХит”.

“Но сегодня самое популярное издание в нашей семье — “Счастливые родители”, и разговоры вертятся вокруг детей, — говорил телеведущий. — Последний раз мы обсуждали, с какой серии развивающего мультика “Ребенок. Эйнштейн” лучше начинать знакомить грудничка, — Baby da Vinci, готовой от­править младенца в музыкальную поезд­ку от вершины его головы к подошвам ног, или ограничиться видео под много­ обещающим названием “Малыш Шек­спир”?

Наталья всегда и во всем поддерживает супруга. Несмотря на то, что Шкулева была беременной, она приходила на съемки первой программы “Андрей Малахов. Прямой эфир”, чтобы увидеть своими глазами начало работы телеведущего на канале “Россия-1”. Почему моя жена заплакала в студии “Прямого эфира”.