В ходе сталинских чисток 1937-1938 годов почти 700 000 человек были приговорены к смертной казни (согласно архивным документам), и все они были осуждены по приказу тогдашнего главы НКВД Николая Ежова. У «кровавого карлика» (его рост составлял всего 150 см) не было собственных детей, но он усыновил дочь Наталью. Несмотря на осуждение со стороны окружающих, она не отказалась от своего приемного отца. Однако было ясно, что у Натальи все-таки были биологические родители, хотя она об этом не знала.
Существует несколько версий о том, как она появилась на свет, в том числе о том, что она была внебрачным ребёнком последней жены Ежова, или что она была внебрачной дочерью самого Ежова, или дочерью семьи советских дипломатов, казнённых НКВД Ежова. Какова бы ни была правда, девочку удочерили в 11 месяцев, и она стала главной отдушиной Ежова. В раннем детстве она была очень слабой и болезненной, поэтому многим показалось странным, что выбрали именно ее.
В 1938 году Евгения Хаютина, жена Николая Ежова, покончила с собой. Через год после этого, сам «железный нарком» был расстрелян. Сначала семилетнюю Наталью отправили в дошкольный детский дом в Пензе. Там ей приписали на два года больше её настоящего возраста и сменили фамилию на Фейгенберг, которую носила Евгения в своем первом браке. Таким образом, Наталья Ежова стала Натальей Хаютиной. Девочке строго запретили вспоминать о приемном отце и даже произносить его фамилию.
Тем не менее, она помнила о нем всегда и позже рассказывала: «Он был потрясающим отцом. Я помню, как он своими руками сделал для меня двухлопастные коньки и научил меня играть в теннис и города. Он проводил со мной много времени». Наталья обожала отца и при любой возможности рассказывала о том, кем она была. Но в конце концов стресс стал невыносимым, и она решила повеситься. Однако верёвка не выдержала. «Всё моё тело было в порезах, платье порвано, а эта верёвка висела у меня на шее», — рассказывала она.
Позже Хаютина добровольно переехала в деревню под Магаданом (8000 км к востоку от Москвы), куда её отец сослал многих своих жертв, чтобы быть ближе к ним. Страна узнала о Наталье летом 1998 года. Тогда Военная коллегия Верховного Суда рассматривала дело о реабилитации бывшего народного комиссара внутренних дел СССР, организатора массовых политических репрессий Николая Ивановича Ежова.
Однако, реабилитировать отца ей не удалось, суд отклонил иск. Там, в Магадане, она сочиняла стихи и песни, редко выходя из дома. Каждый стук в дверь заставлял её вздрагивать: «Я всё ещё думаю, что однажды они постучат в дверь и отомстят мне за то, кем был мой отец». Она скончалась в 2016 году.
