Fatigue deformation behavior of the commercially pure iron containing micro-voids at grain boundaries (GBs) were investigated under total strain amplitude control, and fatigue fractures were quantitatively characterized by fractal analyses. The cyclic response curves of the CP iron show an initial softening stage within early several cycles followed by a continuous cyclic hardening. No stress saturation phenomenon was found. Pre-existence of micro-voids at GBs spurs intergranular cracking to become a common damage mode besides transgranular cracking along slip bands. Quantitative analyses of fracture surface demonstrate that the value of fractal dimension D of the scanning profile in the crack growth zone is the largest as compared to those in the crack source zone and final rapid fracture area, almost regardless of the applied strain amplitude. This phenomenon was discussed in terms of the tortuosity of crack propagation path.