Soil mass stability refers to the ability of soil to resist deformation and failure under external loads, and it is a fundamental consideration in geotechnical engineering, particularly for large-scale infrastructure such as earth-rock dams and slopes. This stability is primarily determined by the soil’s shear strength, which defines the internal resistance of the soil to sliding along potential failure planes. A major challenge in accurately predicting the shear strength of coarse-grained soils is the scale effect, where laboratory test results on small-scale specimens may not fully represent the behavior of large-scale soil masses encountered in real-world applications. To address this issue, this study investigates the influence of two key factors—the maximum particle diameter (dmax) and the gradation structure, quantified by the gradation area (S)—on the shear strength of coarse-grained soils. We designed 21 distinct soil specimens with varying dmax and S values to simulate natural soil gradations, and conducted large-scale triaxial compression tests to explore the relationship between these parameters and shear strength indicators, namely, cohesion (c) and internal friction angle (φ). The results show that increasing dmax enhances both cohesion and internal friction due to stronger interlocking between particles, while a higher gradation area (S), reflecting a broader particle size distribution, reduces these parameters as uneven stress distribution weakens the soil structure. Based on these observations, we propose a shear strength prediction model that incorporates the scale effect, which has been validated using independent datasets from a range of coarse-grained soils.