This paper presents a non-gaited motion planner for humanoid robots navigating very uneven and sloped terrain. The planner allows contact with any pre-designated part of the robot's body, since the use of hands or knees (in addition to feet) may be required to balance. It uses a probabilistic, sample-based approach to compute each step. One challenge of this approach is that most randomly sampled configurations do not satisfy all motion constraints (closed-chain, equilibrium, collision). To address this problem, a method of iterative constraint enforcement is presented that samples feasible configurations much more quickly. Example motions planned for the humanoid robot HRP-2 are shown in simulation. © 2005 IEEE.