Large anions are attracted to hydrophobic surfaces while smaller, well solvated ions are repelled. Using a combination of explicit solvent and continuum model simulations we show that this leads to signifcant ion specifc protein-protein interactions due to hydrophobic patches on the protein surfaces. In solutions of NaI and NaCl we calculate the potentials of mean force and find that the resulting second virial coeffcients for lysozyme corresponds well with experiment. We argue that ionic interactions with non-polar surface groups may play an important role for bio-molecular assembly and Hofmeister type effects.