Experiments and molecular simulations have shown that the hydrophobic mismatch between proteins and membranes contributes significantly to lipid-mediated protein-protein interactions. In this article, we discuss the effect of cholesterol on lipid-mediated protein-protein interactions as function of hydrophobic mismatch, protein diameter and protein cluster size, lipid tail length, and temperature. To do so, we study a mesoscopic model of a hydrated bilayer containing lipids and cholesterol in which proteins are embedded, with a hybrid dissipative particle dynamics-Monte Carlo method. We propose a mechanism by which cholesterol affects protein interactions: protein-induced, cholesterol-enriched, or cholesterol-depleted lipid shells surrounding the proteins affect the lipid-mediated protein-protein interactions. Our calculations of the potential of mean force between proteins and protein clusters show that the addition of cholesterol dramatically reduces repulsive lipid-mediated interactions between proteins (protein clusters) with positive mismatch, but does not affect attractive interactions between proteins with negative mismatch. Cholesterol has only a modest effect on the repulsive interactions between proteins with different mismatch. © 2010 by the Biophysical Society.