Despite fatigue free of monolayer graphene, its assemblies, like cellular graphene aerogels (CGA), are usually suffering of frequent fatigue and inherent strength degradation in repeated loading. In this work, by employing multiscale modeling, the highly intrinsic anisotropic mechanical properties of the cell wall due to the layer-by-layer stacked graphene sheets are uncovered, which easily trigger the unique skeleton joints damage during repeated loading and contribute the primary fatigue mechanism of CGA. Conversely, multiscale joint strengthening strategies are proposed by interlayer crosslinking and joint curvation, improving the interlayer interaction, and decreasing interlayer stress during compression, respectively, so as to effectively suppress joint damage to improve fatigue performance of CGA. This work not only clarifies the underlying fatigue mechanism of 2D cellular materials but also highlights optimal design strategies for developing anti-fatigue graphene cellular structures.