Anti-sliding stability of gravity dams is always a vital topic in dam design and research. A systematic analysis and evaluation of the anti-sliding stability of gravity dams on almost-flatted sandstone-mudstone interbedded foundations is conducted herein and a case study is performed using the main gravity dam of the Julius Nyerere Hydropower Station in Tanzania. First, a comprehensive comparison of the methodology for anti-sliding stability of gravity dams is presented between the Chinese and American design guides or standards. Second, the anti-sliding stability of the Nyerere Dam under critical operating scenarios is analyzed and evaluated by combining the limit equilibrium method and the finite element method. Then, the pros and cons of the aforementioned two methods are discussed in detail. Finally, an integrated analysis method for anti-sliding stability of gravity dams seated on almost-flatted sandstone-mudstone interbedded foundation that combines the advantages of both methods is proposed. The results show that the sliding modes of the Nyerere Dam consist of a rock fracturing surface upstream, a composite sliding surface at the bottom along a combination of the unfavorable weak interlayer and rock shear sliding surface below the shear key, and a shear sliding surface through the resisting rock extended to ground surface downstream. The anti-sliding stability of gravity dams is significantly enhanced by the shear key, which increases the factor of safety by 34%. It is recommended that a multi-angle and all-round anti-sliding stability analysis be carried out under complex operating scenarios through the proposed integrated analysis method and by combining the design principles of the Chinese and American requirements.