Electrostatic interactions can strongly increase the efficiency of protein complex formation. The charge distribution in redox proteins is often optimized to steer a redox partner to the electron transfer active binding site. To test whether the optimized distribution is more important than the strength of the electrostatic interactions, an additional negative patch was introduced on the surface of cytochrome c peroxidase, away from the stereospecific binding site, and its effect on the encounter complex as well as the rate of complex formation was determined. Monte Carlo simulations and paramagnetic relaxation enhancement NMR experiments indicate that the partner, cytochrome c, interacts with the new patch. Unexpectedly, the rate of the active complex formation was not reduced, but rather slightly increased. The findings support the idea that for efficient protein complex formation the strength of the electrostatic interaction is more critical than an optimized charge distribution.