Cohesive sediment is an important component of the aquatic environments, which must be monitored and managed for environment, engineering, and human health reasons. The stability of cohesive sediments in an aquatic environment dependent on the balance between hydrodynamic forces that cause erosion and the forces within the sediment that resist it. And the stability of cohesive sediments is described by the critical shear stress. At present, existing models for the critical shear stress of the surface erosion of cohesive sediments is lacking a consideration of the aggregate size distribution in cohesive sediments. This study constructed the fractal model of the cohesive aggregate structure in cohesive sediments. Meanwhile, the relationship is built for the critical shear stress as functions of the median diameter and excess density from the fractal model for cohesive aggregates. It can be found that the critical shear stress of cohesive sediments is a power function of the median diameter and excess density. The proposed relations from the fractal model for aggregates are validated by a bulk number of experimental data and a new method is proposed to determine the critical shear stress.