A three-dimensional criterion is provided for the estimation of balance stability states of legged robotic systems subject to various constraints. A general framework is established to evaluate the balance stability boundary of a given system in the state space of Center of Mass (COM) Cartesian position and velocity. For each assigned COM initial position, an optimization-based iterative algorithm finds the minimum and maximum COM initial velocity that the system can handle along a given direction, such that it maintains the capability to reach a final static equilibrium. The resulting set of velocity extema constitutes the system's balance stability boundary, which represents the sufficient condition to estimate falling states versus balanced states, according to the definitions provided herein. The COM state space domain identified with this approach contains all possible balanced states for the given legged system, with respect to the necessary physical, balancing, and design constraints. The balance state estimation is demonstrated for 1- and 2-degrees of freedom planar legged systems in single support. The domain identified by the balance stability boundary can be used as a "map" for the given legged system in which the distance from a given state to the domain boundaries can provide a quantitative measure of balance stability/instability.