В 1970 г. окончила Свердловское театральное училище по специальности «Актер драмы и кино», в 1977 - Харьковскую театральную академию по специальности «Режиссура драмы».

Работала в театрах Украины, Казахстана и России.

С 1984 по 1999 годы была доцентом кафедры мастерства актера Екатеринбургского государственного театрального института

Многие выпускники мастерской Натальи Мильченко работают в театрах Екатеринбурга, Новосибирска, Смоленска, Санкт-Петербурга, Москвы и других городов России.

В 1995 году шестеро выпускников мастерской Натальи Мильченко в ЕГТИ и народная артистка России Галина Петрова стали основой труппы нового Театра-Лаборатории драматического искусства имени Михаила Чехова.

Наталья Витальевна возглавила театр.

За годы его работы поставлено более 80-ти спектаклей. Постановки Н.В. Мильченко не раз были отмечены различными наградами. В числе спектаклей – лауреаты и дипломанты Областного театрального фестиваля «Браво», Международного фестиваля «Ламбушка» (Петрозаводск), Международного фестиваля камерных спектаклей по произведениям Достоевского.

В 2004 году, по благословению архиепископа Екатеринбургского и Верхотурского Викентия, театр получил право именоваться православным и стал регулярно участвовать в ежегодном фестивале православной культуры «Царские дни».

Осуществлялось тесное взаимодействие с церковно-приходскими школами, театр регулярно приглашал детей-инвалидов и сирот на благотворительные спектакли, выезжал с гастролями в учреждения исполнения наказания, в приходы Екатеринбургской епархии.

Последние гастроли актеров театра, которые возглавила Наталья Мильченко, состоялись в Верхотурье 22 января.

С 7 июля 2003 года Наталья Витальевна работала на радиоканале «Воскресение», с самого дня его основания, – за эти семь с половиной лет в эфире радиоканала прозвучало огромное количество рассказов, повестей, спектаклей в интерпретации театра имени Чехова.

Множество благодарных откликов было на радиоспектакль «Отец Арсений», на постановки по произведениям Ивана Шмелева, Антона Чехова, Федора Достоевского, Ивана Тургенева. Авторские рубрики Натальи Витальевны «Профессия – театр», «Семейное прослушивание», «Сподвижники ХХ века» собирали у радиоприемников свою обширную аудиторию.

«Поэтическая страничка», в которой духовные стихи читали и актеры, и священники, также была детищем Натальи Витальевны.

Последняя, незавершенная работа Натальи Мильченко и актеров театра имени М. Чехова – радиопостановка по произведению И. Бунина «Окаянные дни». Последней крупной режиссерской работой Натальи Витальевны стал спектакль "Любовь, которая не кончается никогда" (премьера состоялась в Москве, в Театре Драмы и Музыки Стаса Намина).

Благодаря Н.В.Мильченко и ее театру в архиве радиоканала «Воскресение» есть уникальные записи авторских радиоспектаклей. Все они, конечно, будут звучать в эфире. Наталья Витальевна скончалась 23 января 2011года.