In its initial evolution stage, fatigue damage consists of many microdamage sites, having random sizes and locations. The way in which these sites grow and coalesce has a crucial effect on the macro fatigue life. A statistical micromechanic fatigue model has been developed, in which the material is composed of microelements of random strength with a certain probabilistic dispersion parameter (β). In addition, the model takes into account local interactions between damaged microelements and their first neighbors by considering a failure sensitivity factor (c), which is the probability that the neighbor will survive the local (micro) stress concentration. It was shown analytically in previous studies that β is proportional to the S-N power intensity, and ln(1-c) is proportional to the macro endurance limit. In this study, the analysis is generalized to the case where the growth of each micro-damage is size dependent, i.e., each damage site grows at a rate which depends on its current size. The strength of this rate-size relation controls the order of the governing differential equation. It was found that certain “microdamage growth laws” still preserve the macro power law, so that the power on the S-N diagram can be directly related to the local microdamage evolution. While the analytical micro-macro relation is still under current study, a numerical simulation of fatigue damage evolution has been obtained and revealed that the macro S-N power law prevails in spite of the noticable complexity.