Structure prediction of protein-protein complexes is one of the most critical challenges in computational structural biology. It is often difficult to predict the complex structure, even for relatively rigid proteins. Modeling significant structural flexibility in protein docking remains an unsolved problem. This work demonstrates a protein-protein docking protocol with enhanced sampling that accounts for large-scale backbone flexibility. The docking protocol starts from unbound x-ray structures and is not using any binding site information. One protein partner undergoes multiple fold rearrangements, rotations, and translations during docking simulations, while the other protein exhibits small backbone fluctuations. Including significant backbone flexibility during the search for the binding site has been made possible using the CABS coarse-grained protein model and Replica Exchange Monte Carlo dynamics. In our simulations, we obtained acceptable quality models for the set of 12 protein-protein complexes, while for selected cases, models were close to high accuracy.