Natalia Barbu nació en Bălţi el 22 de agosto de 1979, cuando Moldavia aún formaba parte de la URSS. Pasó su infancia en la casa de sus abuelos, en el corazón del bosque norteño del país, hasta que a los 7 años (en pleno conflicto de Transnistria) se mudó a Ribniţa.

Aparte de ir a un colegio rumano acudió al colegio de música Stefan Neaga, en donde aprendió a tocar el violín, instrumento que la acompañará a lo largo de toda su trayectoria. Según palabras textuales de ella no le gustaba y “se sentía torturada y obligada a tocar el violín mientras los demás niños jugaban”; un punto de vista que, como su posterior carrera musical ha demostrado, cambió radicalmente. Tras su graduación en esta escuela, siguió sus estudios de violín en la academia de música Gavriil Muzicescu. Aunque antes de ello, Natalia ya era invitada con tan solo doce años a tocar y cantar en bodas y bautizos.

El conflicto de Transnistria hizo su vida y la de su familia imposible en Ribniţa, así que decidieron mudarse a la capital, Chisinau. Una vez allí, su madre empezó a cantar en el grupo de folk Mugurel y Natalia la acompañó como violinista dentro del grupo. Aunque nunca dejaba el violín de lado, su primera aparición como vocalista fue acompañada por la Orquesta de música folk del instituto al que iba. En 1998, a los 19 años, se presentó a tres festivales de música pop en los que arrasó consiguiendo el primer premio en los tres. Entre ellos, estaba el prestigioso Mamaia ’98 de Rumanía en el que consiguió el Premio de la prensa como Miss festival. En 1999 probó a formar parte de la banda Millenium, pero no duró mucho tiempo porque prefirió continuar su carrera en solitario. Siguió presentándose a diversos festivales tanto en Moldavia como en Rumanía, Ucrania o Bielorrusia en los que, si no ganaba el primer premio, sí obtenía algún reconocimiento.

Tras un breve descanso que parecía romper el que era un prometedor ascenso, en 2001 decidió unir fuerzas con el grupo de músicos Trigon y crear el que sería su primer álbum, Intre ieri si azi, de estilo jazz-folk, y que no pretendía ser un éxito comercial. Natalia escribió las letras de todas las canciones de este álbum y compuso gran parte de ellas. En 2003 consiguió lanzar el álbum Zbor de dor y por fin, en 2005, logró firmar un contrato por tres años con Cat Music de Bucarest. Su mayor éxito en esta compañía discográfica antes del Festival fue el sencillo Ingerul meu, que consiguió mantenerse durante 11 semanas en el número uno del Top 100 de Rumanía.

Al fin, el 14 de diciembre de 2006 se anunció que Natalia Barbu sería la representante de Moldavia en Finlandia con la canción Fight. Con una puesta en escena llamativa y una indumentaria de lo más peculiar, Natalia consiguió que Moldavia volviera a la Final después del mal resultado obtenido en Atenas por Arsenium y Natalia Gordienko, otorgándole a su país su segundo top 10.

La vida de Natalia sigue después de Eurovisión y, tras sacar dos discos en 2009, uno recopilatorio llamado Fight – Best of Natalia Barbu y otro titulado Sunt fata de maritat que consiguió la certificación de Oro, empieza a colaborar en 2012 con el productor musical Radu Sirbu y su hermana, la compositora Ana Sirbu, bajo el sello discográfico Rassada Music. A finales de verano saca su nuevo sencillo I said it’s sad, que supone un importante cambio de estilo para ella y con el que logra conquistar nuevamente el número uno de la lista Top 10 Airplay Moldova. Esta canción se integra en el álbum Iubire cu aroma de cafea, que saca a finales del año 2012.

Confession, una de las canciones de su último álbum, fue la apuesta de Natalia Barbu para volver al Festival de Eurovisión en 2013, aunque esta vez representando a Rumanía. No consiguió pasar de la repesca del Selectia nationala, preselección que ganó el cantante Cezar. Al año siguiente lanzó el sencillo In Too Deep, grabado en el Estudio 26 de Miami (Florida). Desde entonces no ha sacado ningún álbum de estudio pero sí diversos singles: Ai plecat (2014), Noi 2 (2015) y su versión en inglés Don’t Close Your Eyes, Mama (2016), Firefly #LaLaLa (2016), Esti atat de frumoasa (2018), Elegie (2018), La capatul cerului (2020), Iubeste-ma azi (2020) y Simplu (2020). Desde entonces no ha publicado nuevos singles, aunque sí participa en conciertos y eventos promocionales.

En 2024 intentó de nuevo participar en el Festival de Eurovisión, y finalmente fue escogida con la canción In The Middle, con la que Moldavia actuará en la primera semifinal del 7 de mayo en Malmö.  Mientras, asistirá a la preparty de Madrid el día 28 de marzo.

En 2011 Natalia se casó con el empresario multimillonario Nicolae Sota, con el que vive desde entonces en Rumanía. En diciembre de 2015 fue nombrada como la mujer viva más sexy de Moldavia por la revista Esquire.