Designing controllers for legged locomotion requires dealing with complex nonlinear dynamics and non-trivial notions of stability including limit cycles and dynamically stable maneuvers. In this talk I will describe the LQR-Trees algorithm for designing feedback controllers for legged robots navigating on flat and rough terrain. The algorithm combines randomized motion planning and trajectory optimization algorithms, popular in robotics, with rigorous tools from control theory for verifying regional stability of nonlinear systems. The algorithm can efficiently handle limit cycles, impacts, trigonometric nonlinearities, and saturations. Under mild assumptions, it probabilistically converges to a feedback which stabilizes the entire controllable state space; guaranteeing that every initial condition which can be stabilized to the nominal limit cycle or goal will be stabilized to that goal.