Natalia Gordienko (ukrainisch Наталя Гордієнко, Natalja Hordijenko; * 11. Dezember 1987 in Chișinău, Moldauische SSR) ist eine moldauische Sängerin ukrainischer Abstammung.
Natalia Gordienko verfügt über einen Musikschulabschluss als Pianistin und erwarb 2006 ihr Abitur. Von 2003 bis 2005 nahm sie erfolgreich an nationalen Musikwettbewerben teil, 2004 wurde sie zur moldauischen Miss Teenager erkoren. Im Vorfeld der ersten moldauischen Teilnahme am Eurovision Song Contest 2005 nahm sie als Leadsängerin der Band Millennium mit dem Titel Tablou pe sticlă an der nationalen Vorentscheidung teil, unterlag aber der Band Zdob și Zdub.
Sie trat zusammen mit dem Popsänger Arsenium (Ex-Mitglied der Band O-Zone) beim Eurovision Song Contest 2006 mit dem Titel Loca für Moldau an und belegte dort im Finale den 20. Platz. Im nationalen Vorentscheid am 15. März 2006 hatte das Duo zuvor sowohl von der Jury als auch vom Publikum die Höchstwertung erhalten.