We present an algorithm for computing stable collision-free motions for humanoid robots given full-body posture goals. Given a robot's internal model of the environment and a statically-stable desired posture, we use a randomized path planner to search the configuration space of the robot for a collision-free path. Balance constraints are imposed on incremental search motions in order to maintain the overall dynamic stability of the computed trajectories. An overview of the algorithm is presented along with preliminary results using an experimental implementation on a dynamic model of the H6 humanoid robot.