The club was founded on October 12, 1917. They won the Campeonato Fluminense in 1959, when they beat Goytacaz in the final. They won the Campeonato Fluminense for the second time, in 1960, after Goytacaz forfeited the final. The club competed in the same year in the Taça Brasil, being eliminated in the First Round by Fluminense. They competed in the Taça Brasil again in 1961, when they were eliminated in the First Round by America. Fonseca won the Campeonato Fluminense for the third time, in 1962, after beating Rio Branco de Campos in the final. The club competed for the third time in the Taça Brasil in 1963, when they were eliminated in the First Round by Rio Branco-ES.