The discovery that the functions of most eukaryotic gene products are mediated through multi-protein complexes makes the prediction of protein interactions one of the most important current challenges in structural biology. Rigid-body docking methods can generate a large number of alternative candidates, but it is difficult to discriminate the near-native interactions from the large number of false positives. Many different scoring functions have been developed for this purpose, but in most cases, experimental and biological information is still required for accurate predictions. We explore here the use of evolutionary restraints in evaluating rigid-body docking geometries. In order to identify potential interface residues we identify functional residues based on the comparison of observed amino acid substitutions with those predicted from local environment. The interface residues identified by this method are correctly located in 85% of the cases. These predicted interface residues are used to define distance restraints that help to score rigid-body docking solutions. We have developed the pyDockRST software, which uses the percentage of satisfied distance restraints, together with the electrostatics and desolvation binding energy, to identify correct docking orientations. This methodology dramatically improves the docking results when compared to the use of energy criteria alone, and is able to find the correct orientation within the top 20 docking solutions in 80% of the cases.