De club werd in 1960 opgericht als EC Baraúnas, in 1966 werd de huidige naam aangenomen. In 2005 nam de club voor het eerst deel aan de Copa do Brasil en versloeg er in de eerste ronde América Mineiro, daarna zette de club ook grote namen als Vitória en Vasco da Gama opzij alvorens zelf uitgeschakeld te worden in de kwartfinale door Cruzeiro. Een jaar later speelde de club in de finale van het staatskampioenschap tegen stadsrivaal Potiguar. Het was de eerste keer sinds de oprichting van het staatskampioenschap in 1919 dat er niet ten minste één club uit Natal bij de eerste twee eindigde. Beide finales eindigden op 0-0 en omdat Baraúnas beter presteerde in de competitie kregen zij de titel toegewezen.
