Association of two biological macromolecules is a fundamental biological phenomenon and an unsolved theoretical problem. Docking methods for ab initio prediction of association of two independently determined protein structures usually fail when they are applied to a large set of complexes, mostly because of inaccuracies in the scoring function and/or difficulties on simulating the rearrangement of the interface residues upon binding. In this work we present an efficient pseudo-Brownian rigid-body docking procedure followed by Biased Probability Monte Carlo Minimization of the ligand interacting side chains. The use of a soft interaction energy function pre-calculated on a grid, instead of the explicit energy, increased drastically the speed of the procedure. The method was tested on a benchmark of twenty-four protein-protein complexes where the 3D structures of their subunits (bound and free) were available. The rank of the near-native conformation in a list of candidate docking solutions was below 20 in 85 % of complexes with no major backbone motion upon binding. Among them, as many as seven protease-inhibitor complexes out of eleven (64 %) can be successfully predicted as the highest rank conformations. The presented method can be further refined to include the binding site predictions and applied to the structures generated by the structural proteomics projects. All scripts are web available.