The rational modification of protein stability is an important goal of protein design. Protein surface electrostatic interactions are not evolutionarily optimized for stability and are an attractive target for the rational redesign of proteins. We show that surface charge mutants can exert stabilizing effects in distinct and unanticipated ways, including ones that are not predicted by existing methods, even when only solvent-exposed sites are targeted. Individual mutation of three solvent-exposed lysines in the villin headpiece subdomain significantly stabilizes the protein, but the mechanism of stabilization is very different in each case. One mutation destabilizes native-state electrostatic interactions but has a larger destabilizing effect on the denatured state, a second removes the desolvation penalty paid by the charged residue, whereas the third introduces unanticipated native-state interactions but does not alter electrostatics. Our results show that even seemingly intuitive mutations can exert their effects through unforeseen and complex interactions.