The club was founded on June 5, 1904 by a group of alumni of the Colegio Nacional de la Capital, one of the oldest public schools in Asunción. The club was originally named Nacional Football Club, taking the name "Nacional" from the school the founders attended. Its first president was Víctor Paredes Gómez and white was selected as the team color because that was the color of the Nacional de la Capital School uniform. For the emblem of the club, the colors of the Paraguayan flag were chosen.
Nacional is one of the traditional teams in the Paraguayan league and they have won a total of nine championships so far. Their nickname "La Academia" (the academy) was given to them because of their excellent youth system that produced great players such as Arsenio Erico, who is considered as the best Paraguayan footballer of all time.
In 2009 Nacional won the Clausura 2009 title after 63 years.