Entidad fuertemente arraigada al barrio obrero de La Teja, portadora de una profunda identidad anarcosindicalista y de un título histórico de Primera División en la temporada de 1989.
El 30 de abril de 1917, un grupo de trabajadores pertenecientes al gremio de picapedreros de La Teja concretó la fundación oficial de la entidad deportiva en Montevideo, tras organizarse inicialmente en las instalaciones del conventillo Balaro por gestión de José Vázquez. El maestro de escuela Héctor Verdesio asumió como el primer presidente de la institución. Eligieron diseñar el uniforme titular con franjas rojas y amarillas como un homenaje directo a los colores de Cataluña, territorio de origen de los principios anarcosindicalistas compartidos por la mayoría de los trabajadores de la zona.
Tras la utilización de campos nómades y baldíos del barrio para oficiar sus encuentros, el club inauguró en el año 1926 su primer predio deportivo formal. En la década de 1930, la asamblea de socios logró consolidar y asegurar los derechos sobre el recinto en La Teja de forma definitiva. La dirigencia decidió bautizar las instalaciones de entrenamiento y competencia como Parque Abraham Paladino a modo de reconocimiento póstumo hacia la figura del expresidente y socio que colaboró operativamente en mantener al club a flote en sus peores carencias económicas.
Tras organizar el funcionamiento del plantel principal dentro del certamen de Segunda División en 1979, la institución logró establecer un sistema sólido de resultados. Jugando con su localía en La Teja, dominó el esquema y sumó una contundente racha consecutiva de victorias. Al finalizar el calendario del torneo, el equipo obtuvo los puntos necesarios en la última fecha para coronarse campeón del certamen de ascenso, garantizando el salto a la máxima categoría del fútbol uruguayo de forma definitiva.
Durante la temporada 1989, bajo la presidencia del Dr. Tabaré Vázquez y la dirección técnica de Saúl Rivero, el modesto equipo de La Teja superó a los clubes de mayor presupuesto del país. En un formato de temporada cerrado de trece fechas en única rueda, Progreso completó el calendario invicto y logró el puntaje más alto, consolidándose como Campeón Uruguayo absoluto en Primera División. Esta gesta constituyó el primer título de campeonato originado netamente fuera de la hegemonía institucional central del país.
El título de campeonato de 1989 posibilitó su estreno continental, clasificando al club a la fase de grupos de la Copa Libertadores de América de 1990. Progreso integró el cuadro junto a los representantes peruanos Unión Huaral y Sporting Cristal, además de Defensor Sporting. Tras clasificar superando la fase inicial de puntos, alcanzó la histórica etapa directa de los octavos de final. En este tramo decisivo se enfrentó ante el Barcelona de Ecuador, despidiéndose del torneo tras una dramática eliminación por tiros penales.