Both natural and synthetic polyelectrolytes form strong complexes with a variety of proteins. One peculiar phenomenon is that association can take place even when the protein and the polyelectrolyte carry the same charge. This has been interpreted as if the ion-dipole interaction can overcome the repulsive ion-ion interaction. On the basis of Monte Carlo simulations and perturbation theory, we propose a different explanation for the association, namely, charge regulation. We have investigated three different protein-polymer complexes and found that the induced ionization of amino acid residues due to the polyelectrolyte leads to a surprisingly strong attractive interaction between the protein and the polymer. The extra attraction from this charge-induced charge interaction can be several kT and is for the three cases studied here, lysozyme, alpha-lactalbumin, and beta-lactoglobulin, of the same magnitude or stronger than the ion-dipole interaction. The magnitude of the induced charge is governed by a response function, the protein charge capacitance < Z(2)> - < Z >(2). This fluctuation term can easily be calculated in a simulation or measured in a titration experiment.