The Korydallos-based club was founded in the northern Piraeus suburb in the 1920s by refugees from Asia Minor. Its emblem is the mythological phoenix bird arising from its ashes and the teams colour is maroon. During the era of local championships, Proodeftiki played a leading role in the Piraeus league.
Proodeftiki has had several stints in the Football A Division of the National Championship starting from the very first (1959 - 1960). Their best season was 1965 when, as a newly-promoted team, they finished 4th shocking Olympiakos in the process 3-0 in Karaiskaki Stadium.