Predicting the structure of protein-protein complexes using docking approaches is a difficult problem whose major challenges include identifying correct solutions, and properly dealing with molecular flexibility and conformational changes. Flexibility can be addressed at several levels: implicitly, by smoothing the protein surfaces or allowing some degree of interpenetration (soft docking) or by performing multiple docking runs from various conformations (cross or ensemble docking); or explicitly, by allowing sidechain and/or backbone flexibility. Although significant improvements have been achieved in the modeling of sidechains, methods for the explicit inclusion of backbone flexibility in docking are still being developed. A few novel approaches have emerged involving collective degrees of motion, multicopy representations and multibody docking, which should allow larger conformational changes to be modeled.