Their first national appearance was in 2003. Their first match was a scoreless draw with Amabox Barcelona on May 18. A week later on May 24, Paulense scored their first national champs goal in a match with Cutelinho of Fogo who Paulense lost. On June 14, Paulense made their first national champ win over Boa Vista's Académica Operária 2–1. Paulense lost the final match of the season to Mindelo's Batuque and finished fourth with a win and a draw and had four points and was out of the competition after being outside the qualification zone of the playoff stage. Paulense made their second appearance in 2004 and was unsuccessful almost as last season, they made just a win over Santiago North's Estrela dos Amadores 3–0 on May 22 where they scored all the season's goals. On May 29, Paulense made their worst defeat ever, they lost to Sal's Académico do Aeroporto on May 29. Their third appearance was made in 2005, their first match was a won over São Nicolau's Desportivo Ribeira Brava and was 0–3 on May 14. They made their only draw on May 21 and was two goals with Académica do Fogo. The next two matches ended in losses and thus another unsuccessful season for the club. The final match of the season featured champion of the Santiago North Zone Flor Jovem da Calheta and did not play as Paulense was fourth with only four points, six behind Académica Fogo's and Flor Jovem, a weak team withdrew from the competition. On June 19, Paulense was out of the competition.