Electron backscattering diffraction, EBSD, technique as well as atomic force microscopy, AFM, was employed to investigate fatigue damage mechanism in ultrafine-grained copper processed by equal channel angular pressing, ECAP. The fatigue damage evolution under axial tension compression was investigated. The results show that linearly shaped fatigue damage was introduced in the scale of micrometers in spite of the average grain size of 300 nm. The linear damage was randomly oriented when the shear direction of the last ECAP-pressing in perpendicular to the loading axis. The orientation analysis by EBSD revealed that the linear damage is introduced in the area with the same crystallographic orientation in the direction of the maximum Schmid factor as in the slip deformation in coarse-grained materials. The comparison before and after fatigue tests shows the grain coarsening in the area where large linear fatigue damage was formed. It is considered that strain concentration at the edge of the slips introduced in a relatively coarse ultrafine grain causes the grain rotation and deformation in the adjacent nano-sized grains, resulting in the grain coarsening and subsequent propagation of the slips in the order of micrometers.