This study investigates the influence of the embedment depth of rigid footings resting on rock slopes on the ultimate bearing capacity and evaluates the corresponding failure mechanisms. In most previous studies, the embedment depth was assumed to be the depth at which the footings were placed on the ground surface and simplified by applying an equivalent surcharge. This simplification neglects the shear strength of the embedding rock mass, leading to an underestimation of the ultimate bearing capacity of the footings. Therefore, an adaptive finite-element limit analysis (FELA), including both lower and upper bound simulations, is employed; in particular, the rock mass is assumed to follow the modified Hoek–Brown failure criterion. A set of influential parameters, including the embedment depth ratio, the edge distance ratio, the slope gradient, and the geotechnical parameters of the Hoek-Brown criterion, is introduced to conduct detailed parametric studies. The results indicate that the ultimate bearing capacity increases linearly with the embedment depth of the footings, a trend that cannot be accurately predicted by methods that replace the embedment depth with an equivalent surcharge. Three typical failure patterns were observed in the rock slope-footing system; design tables featuring these identified failure patterns are presented to aid in engineering design.