In order to study the effect of trace impurities on high-cycle fatigue damage of ultrafine grained (UFG) copper, fatigue tests were carried out for two samples: oxygen-free copper (OFC, 99.99 wt% Cu) and deoxidized low-phosphorous copper (DLP, 99.95 wt% Cu). After the processing by equal channel angular pressing (ECAP) using eight passes, equiaxed grains with an average size of 250 nm were formed for both the samples. Fatigue strength of UFG copper was enhanced by the impurities. The formation behavior of surface damage and the change in surface hardness was monitored. A close relationship was observed between the change in hardness and the formation behavior of surface damage. The physical background of the effect of trace impurities on the fatigue damage was discussed from the viewpoints of surface damage formation behavior.