A theoretical model is presented for the free energy ΔGb of complex formation between a highly charged polyelectrolyte and a protein. The model introduced here comprises both the effect of released counterions and the uptake or release of water molecules during complex formation. The resulting expression for ΔGb is hence capable of describing the dependence of ΔGb on temperature as well as on the concentration of salt in the system: An increase of the salt concentration in the solution increases the activity of the ions and counterion release becomes less effective for binding. On the other hand, an increased salt concentration leads to the decrease of the activity of water in bulk. Hence, release of water molecules during complex formation will be more advantageous and lead to an increase of the magnitude of ΔGb and the binding constant. It is furthermore demonstrated that the release or uptake of water molecules is the origin of the marked enthalpy–entropy cancellation observed during complex formation of polyelectrolytes with proteins. The comparison with experimental data on complex formation between a synthetic (sulfated dendritic polyglycerol) and natural polyelectrolytes (DNA; heparin) with proteins shows full agreement with theory.