The LY12CZ aluminum alloy specimens were corroded under the conditions of different test temperatures and exposure durations. After corrosion exposure, fatigue tests were performed. Scanning electron microscopy and optical microscope analyses on corrosion damage were carried out. The definition of surface corrosion damage ratio was provided to describe the extent of surface corrosion damage. On the basis of the measured data sets of the corrosion damage ratio, the probabilistic model of corrosion damage evolution was built. The corrosion damage decreased the fatigue life by a factor of about 1.25 to 2.38 and the prediction method of residual strength of the corroded structure was presented.