В 1999 году Наталия Романенко приехала в Париж для дальнейшего обучения. Она училась у Оливье Гардона и Жака Рувье и выиграла первую премию Консерватории Парижа в 2001 году.
Аккомпаниатор в Консерватории Парижа, Наталия Романенко стремится вернуть этой профессии былой блеск и вывести её на передний план. В интервью, которое она дала журналу La lettre du musician, она цитировала Альфреда Бренделя и Даниэля Баренбойма. Но, «чувствуя себя комфортно со всеми композиторами, особенно с удивительной русской музыкой и Листом» (La Marseillaise, 26/10/2003), она посвящает большую часть своего времени концертам.
В 2003 году, в честь 300летия города Санкт-Петербурга, она дала концерт для официальных делегаций России и Франции в Шереметевском дворце. Пресса была в восторге. В 2005 году, по просьбе Юрия Башмета, она выступила в театре Ла Фениче в Венеции. В том же году она также встретилась с виолончелистом Мстиславом Ростроповичем, который, послушав её, заявил, что «она — новая Ванда Ландовска!». Он также попросил её быть его аккомпаниатором на его конкурсе виолончелистов в Париже.
В 2007 году Наталия Романенко совершила концертный тур по Центральной Америке, организованный Альянс Франсез и Culturesfrance. Ежедневная газета La Nacion написала 26 февраля 2007 года: «Наталия Романенко демонстрирует впечатляющие навыки и уникальную симбиозу с её пианино». А El diario de Hoy: «ещё молодая, Наталия Романенко уже имеет не только великое прошлое, но и великое будущее».
В 2009 году Наталия Романенко записала 5-й концерт Антона Рубинштейна с Национальным оркестром Канн (PACA) и его дирижёром Филиппом Бендером. В 2010 году она открыла Год Франции – России в Московской консерватории в престижном зале Чайковского, исполнив 5-й концерт для фортепиано с оркестром Сен-Санса под управлением Жан-Франсуа Эссера.
Она также создала ассоциацию Extraordinaria Classica для продвижения непризнанных и забытых композиторов.