Born in Sete Lagoas, Minas Gerais, she lived in a farm with her parents and her younger brother during her childhood. Fernandes started singing when she was eight years old, releasing her self-titled debut album two years later. Her second album, named Ana Rayo, was released in 1995, and was inspired by the A História de Ana Raio e Zé Trovão telenovela. Fernandes went to college to study Geography in Belo Horizonte when she was 18 years old, singing in pubs during this time. She recorded one of the theme songs of Rede Globo's telenovela América, named "Ave Maria Natureza", and released the album Canções do Vento Sul soon after that. Fernandes was nominated for the Best Popular Singer Award at Prêmio da Música Brasileira with that album. The song "Jeito do Mato" from her following album, Pássaro de Fogo, was a theme song in the Globo telenovela Paraíso, and her version of Ivete Sangalo's "Quando a Chuva Passar" was the main theme of the telenovela Escrito nas Estrelas. Fernandes released her first DVD in October 2010, and gained further recognition after she participated in two Rede Globo specials: the Roberto Carlos' end of year show, broadcast on December 25, 2010, and Show da Virada, broadcast during New Year's Eve, on December 31, 2010. Her live album, Paula Fernandes - Ao Vivo, released in 2011, was the top seller of that year, with over 2,000,000 copies sold according to the ABPD. Fernandes became known in the rest of Latin America due to her collaboration on the Juanes song "Hoy Me Voy", released in his 2012 MTV Unplugged album.