The seismic sliding limit condition of gravity retaining walls with cohesionless soil backfill is investigated and analytical solutions for the critical acceleration coefficient are provided in this paper. The solutions have been derived in the framework of the upper bound theorem of limit analysis. The retaining walls and the backfill soil are taken as a whole system and the combined action of horizontal and vertical accelerations are considered. For retaining walls with horizontal backfill, the effects of the inclination of the wall internal face and of the soil–wall friction were investigated. The effects of vertical component of the seismic acceleration on the yield horizontal acceleration coefficient were discussed in detailed. Based on a limited parametric study, it is shown that both the roughness and inclination of the internal wall face have some effects to the seismic stability of the wall–soil system. And under some conditions, the effects of vertical acceleration are considerable large and can’t be neglected.