We present a trajectory optimization framework for legged locomotion on rough terrain. We jointly optimize the center of mass motion and the foothold locations, while considering terrain conditions. We use a terrain costmap to quantify the desirability of a foothold location. We increase the gait’s adaptability to the terrain by optimizing the step phase duration and modulating the trunk attitude, resulting in motions with guaranteed stability. We show that the combination of parametric models, stochastic-based exploration and receding horizon planning allows us to handle the many local minima associated with different terrain conditions and walking patterns. This combination delivers robust motion plans without the need for warm-starting. Moreover, we use soft-constraints to allow for increased flexibility when searching in the cost landscape of our problem. We showcase the performance of our trajectory optimization framework on multiple terrain conditions and validate our method in realistic simulation scenarios and experimental trials on a hydraulic, torque controlled quadruped robot.