O Treze participou duas vezes a Copa do Brasil, a primeira em 1999 o Treze desclassificou o Santa Cruz-PE de forma surpreendente na primeira fase, e na segunda por pouco não desclassificou o Corinthians-SP, o Galo foi o primeiro time paraibano a se classificar a uma segunda fase de Copa do Brasil. A segunda foi em 2000, o Treze foi prejudicado pela arbitragem nos dois jogos  contra o ABC-RN, impedindo a classificação do Treze para a segunda fase. O Treze já está garantido na Copa do Brasil 2001.