The unit cell model of three-dimensional and four-directional braided composites with an octagonal fiber cross section is established. Based on the fatigue residual stiffness and strength model of unidirectional composites, the fatigue life prediction model of three-dimensional and four-directional braided composites is created by combining the fatigue failure criteria and performance damping method of component materials. The fatigue life prediction and progressive damage analysis program is developed by using ABAQUS finite element software UMAT to simulate the fatigue life and damage propagation process of three-dimensional and four-directional braided composites under fatigue loading. The results show that fatigue damage starts from the elements of contact area between the fiber bundles, and then it spreads to the surface and interior of fiber bundles. Moreover, the damage propagation accelerates with the increase of stress level. This is a new way for predicting the fatigue life of three-dimensional and four-directional braided composites.