This paper considers the problem of planning the motion of a humanoid robot that must execute a manipulation task, possibly requiring stepping, in environments cluttered by obstacles. The proposed method explores the submanifold of the configuration space that is admissible with respect to the assigned task and at the same time satisfies other constraints, including humanoid equilibrium. The exploration tree is expanded using a hybrid scheme that simultaneously generates footsteps and whole-body motions. The algorithm has been implemented for the humanoid robot NAO and validated through planning experiments and dynamic playback in V-REP.