Der Treze Futebol Clube wurde am 7. September 1925 von Antônio Fernandes Bioca, sowie 12 weiteren Fußballfreunden, gegründet. Es war der erste Fußballverein des Staates Paraíba. Das erste Logo war eine 13, um an die 13 Gründer zu erinnern.
Das erste Spiel des neu gegründeten Vereins fand am 6. November 1925 gegen einen örtlichen Rivalen statt und wurde 1:0 gewonnen. In den Jahren 1976, 1977, 1979, 1982 sowie 1983 spielte Treze in der Campeonato Brasileiro de Futebol.
Auf nationaler Ebene waren die größten Erfolge die Aufstiege in die 1. Liga sowie der Gewinn der Campeonato Brasileiro Série B (in der Gruppe E) im Jahr 1986.
