Ana e Vitória estudaram na mesma escola em [[Araguaína]]. Em 2013, já universitárias (Ana cursava medicina e Vitória direito), passaram a gravar despretensiosos vídeos interpretando canções de seus artistas favoritos. Os vídeos não eram ainda assinados como Anavitória, mas sim como "Ana Caetano feat. Vitória Falcão".
Foram descobertas em Novembronovembro de 2014 pelo produtor e empresário artístico Felipe Simas,<ref>{{citar web|obra=Na Pilha|url=http://www.napilha.com/post/anavitoria-o-duo-de-pop-rural-mais-querido-do-momento-|título=Anavitória, o duo de pop rural mais querido do momento!|último =Andrade|primeiro =Luana|data=9 de setembro de 2016}}</ref> após enviarem a ele um vídeo delas interpretando a música "Um Dia após o Outro" de [[Tiago Iorc]], cantor cuja carreira é gerenciada por FelipeSimas. Encantado com o que viu, Felipe logo as convidou para gravarem um EP e chamou Tiago para produzir esse trabalho. Juntos, TiagoIorc e FelipeSimas criaram o selo "Forasteiro" para lançar artistas destacados e batizaram o duo de Anavitória.<ref>{{citar web|obra=OlhoVivo|url=http://www.olhovivoca.com.br/musica/3394/selo-do-cantor-tiago-iorc-apresenta-anavitoria/|título=Selo do cantor Tiago Iorc apresenta Anavitória|último =Tunes|primeiro =Márcia|data=2 de abril de 2015}}</ref> O EP ''[[Anavitória (EP)|Anavitória]]'' foi lançado em 2 de abril de 2015 e conta com duas músicas próprias ("Singular" e "Chamego Meu") e duas regravações ("Cores", da mineira Lorena Chaves, e "Tententender" do duo gaúcho Pouca Vogal). O vídeo de uma cativante performance ao vivo de “Singular” foi postado junto com o lançamento do EP e virou imediatamente um fenômeno na internet.
