Kelly moved to Austria from the US at the age of six in 2000. The daughter of an American businessman with Austrian and Irish roots and a Brazilian mother, Kelly started from an early age with music. In 2004, at the age of ten, she was a member of the children's opera in the production of In 80 Tagen um die Welt (Around the World in 80 Days) at the Baden state theatre. Also in 2004, Kelly came second on Österreichischer Rundfunk (ORF) television show, Kiddy Contest, with a duet with Manuel Gutleb. In the following years, Kelly participated in several competitions including Prima La Musica in classical music.
In 2011, Kelly won a long-running Austrian talent show called The Voice (not to be confused with the international franchise The Voice), and received a recording contract from Alexander Kahr.
2013: Eurovision Song Contest and Natália Kelly
On 15 February 2013, Kelly entered the Austrian national selection for the Eurovision Song Contest 2013, Österreich rockt den Song Contest, with her song "Shine". At the close of voting, Kelly had received 32 points from the jury vote, and 38 points from the televote, giving a total of 70 points and first place, and thus she was selected to represent Austria at the Eurovision Song Contest in Malmö, Sweden. Kelly competed in the first semi-final of the competition on 14 May 2013, however, Austria missed out on qualification for the final, placing 14th in a field of 16 and scoring 27 points. Her debut album entitled Natália Kelly was released worldwide on 12 April 2013.