The permeability of lipid membranes for metabolic molecules or drugs is routinely estimated from the solute’s oil/water partition coefficient. However, the molecular determinants that modulate the permeability in different lipid compositions have remained unclear. Here, we combine scanning electrochemical microscopy and molecular-dynamics simulations to study the effect of cholesterol on membrane permeability, because cholesterol is abundant in all animal membranes. The permeability of membranes from natural lipid mixtures to both hydrophilic and hydrophobic solutes monotonously decreases with cholesterol concentration [Chol]. The same is true for hydrophilic solutes and planar bilayers composed of dioleoyl-phosphatidylcholine or dioleoyl-phosphatidyl-ethanolamine. However, these synthetic lipids give rise to a bell-shaped dependence of membrane permeability on [Chol] for very hydrophobic solutes. The simulations indicate that cholesterol does not affect the diffusion constant inside the membrane. Instead, local partition coefficients at the lipid headgroups and at the lipid tails are modulated oppositely by cholesterol, explaining the experimental findings. Structurally, these modulations are induced by looser packing at the lipid headgroups and tighter packing at the tails upon the addition of cholesterol.