We aim at planning multi-contact sequences of stances and postures for humanoid robots. The output sequence defines the contact transitions that allow our robot to realize different kind of tasks, ranging from biped locomotion to dexterous manipulation. The central component of the planning framework is a best-first algorithm that performs a search of the contacts to be added or removed at each step, following an input collision-free guide path, and making calls to an optimization-based inverse kinematics solver under static equilibrium constraints. The planner can handle systems made of multiple robots and/or manipulated objects through a centralized multi-agent approach, opening the way for multi-robot collaborative locomotion and manipulation planning. Results are presented in virtual environments, with discussion on execution on the real robot HRP-2 in an example situation.