The effects of cholesterol (Chol) on phospholipid bilayers include ordering of the fatty acyl chains, condensing of the lipids in the bilayer plane, and promotion of the liquid-ordered phase. These effects depend on the type of phospholipids in the bilayer and are determined by the nature of the underlying molecular interactions. As for Chol, it has been shown to interact more favorably with sphingomyelin than with most phosphatidylcholines, which in given circumstances leads to formation of lateral domains. However, the exact origin and nature of Chol-phospholipid interactions have recently been subjects of speculation. We examine interactions between Chol, palmitoylsphingomyelin (PSM) and palmitoyl-oleoyl-phosphatidylcholine (POPC) in hydrated lipid bilayers by extensive atom-scale molecular dynamics simulations. We employ a tailored lipid configuration: Individual PSM and Chol monomers, as well as PSM-Chol dimers, are embedded in a POPC lipid bilayer in the liquid crystalline phase. Such a setup allows direct comparison of dimeric and monomeric PSMs and Chol, which ultimately shows how the small differences in PSM and POPC structure can lead to profoundly different interactions with Chol. Our analysis shows that direct hydrogen bonding between PSM and Chol does not provide an adequate explanation for their putative specific interaction. Rather, a combination of charge-pairing, hydrophobic, and van der Waals interactions leads to a lower tilt in PSM neighboring Chol than in Chol with only POPC neighbors. This implies improved Chol-induced ordering of PSM’s chains over POPC’s chains. These findings are discussed in the context of the hydrophobic mismatch concept suggested recently.