Computational protein-protein docking methods currently can create models with atomic accuracy for protein complexes provided that the conformational changes upon association are restricted to the side chains. However, it remains very challenging to account for backbone conformational changes during docking, and most current methods inherently keep monomer backbones rigid for algorithmic simplicity and computational efficiency. Here we present a reformulation of the Rosetta docking method that incorporates explicit backbone flexibility in protein-protein docking. The new method is based on a "fold-tree" representation of the molecular system, which seamlessly integrates internal torsional degrees of freedom and rigid-body degrees of freedom. Problems with internal flexible regions ranging from one or more loops or hinge regions to all of one or both partners can be readily treated using appropriately constructed fold trees. The explicit treatment of backbone flexibility improves both sampling in the vicinity of the native docked conformation and the energetic discrimination between near-native and incorrect models.