The club was founded in 1913 by a group of young friends that chose white and green as the colors in representation of "purity" and "hope", respectively. After its foundation Rubio Ñu joined the rebel league "Liga Centenario", which was created by some clubs that had disagreements with the Paraguayan football association (APF) which was in charge of organizing the main league, the Liga Paraguaya. Some 23 years after its foundation, two others clubs from the same Santísima Trinidad neighborhood (Club Itá Ybaté and Club Flor de Mayo) merged with Rubio Ñu. Sportivo Trinidense (which is also from the same neighborhood) is the club's main rival.
After the Liga Centenario disappeared, they were back in the lower divisions of the Liga Paraguaya until finally in 1926 they won the second division and made their way to the first division. Since then, Rubio Ñu has been relegated and promoted between the third, second and first division several times. Most recently in 2008, they won the second division tournament for the 7th time in their history under the coaching of Francisco Arce and made it to the top-flight of Paraguayan football in 2009.