Plaza are the most successful team from the department of Colonia. They gained their affiliation with AUF in 2000. In 2001 they won promotion to the Primera División Uruguaya and in their debut season they finished in 7th place.
In 2005 the club finally fell to the Decond Division after a poor campaign. In 2006 they did not presented to the championship because of a lack of economic resources.
They re-entered official competitions for the 2006/2007 season, playing once more in the Uruguayan 2nd Division.
Plaza's city rivals are Juventud Colonia, and department derby is against Deportivo Colonia.