Optimal gait planning is applied in this work to the problem of improving stability in quadruped locomotion. In many settings, it is desired to operate legged machines at high performance levels where rapid velocities and a changing environment make stability of utmost concern. Since gait planning still remains a vital component of legged system control design, an efficient method of determining periodic paths is presented which optimize a dynamic stability criterion. Efficient recursive multibody algorithms are used with numerical optimal control software to solve the minimax performance stability criteria.