Cyclic fatigue damage in random short-fiber composites is studied experimentally and analytically. In the experimental phase of the study, the fatigue damage is observed to involve various forms of microcracking, originated from microscopic stress concentrators in the highly heterogeneous microstructure. In the analytical portion of the study, a probabilistic treatment of the microcracks is conducted to evaluate the statistical nature of the microscopic fatigue damage. The density and the cumulative distribution of microcrack lengths are found to follow the well known Weibull-form function, and the microcrack orientation density and cumulative distribution have expressions of a fourth-order power form of the cosθ function. Fatigue damage evolution and accumulation in the random short-fiber composite are analyzed in detail through the development of probabilistic microcrack density and distribution functions during the cyclic loading history.