We present a novel method for solving posture generation problems in multi-contact motion planning for legged robots. Our approach builds on the state of the art by generating not only optimal contact placement locations but also simultaneously verifying the existence of a feasible trajectory allowing the robot to make those contacts. By optimising the robot’s velocity rather than its configuration, we are able to replace what would otherwise be a highly constrained non-linear optimisation problem with a series of linearly constrained quadratic programs, which are comparatively much faster to solve. We implement our posture generator as part of a receding horizon multi-contact planning algorithm to generate several motion plans in challenging environments, including chimney climbing and negotiating narrow passages by forming contacts on walls. Using Bayesian data analysis, we find that the mean execution time of our planner is faster than the state of the art in all scenarios tested (ranging from 10 s to 10 min faster), while in two of four scenarios it returns shorter paths (ranging from 23.4 stance changes longer to 53.9 stance changes shorter).