Inelastic neutron scattering was used to study the effect of 5 and 40 mol% cholesterol on the lateral nanoscale dynamics of phospholipid membranes. By measuring the excitation spectrum at several lateral q (||) values (up to q (||) = 3 Å(-1)), complete dispersion curves were determined of gel, fluid and liquid-ordered phase bilayers. The inclusion of cholesterol had a distinct effect on the collective dynamics of the bilayer's hydrocarbon chains; specifically, we observed a pronounced stiffening of the membranes on the nanometer length scale in both gel and fluid bilayers, even though they were experiencing a higher degree of molecular disorder. Also, for the first time we determined the nanoscale dynamics in the high-cholesterol liquid-ordered phase of bilayers containing cholesterol. Namely, this phase appears to be "softer" than fluid bilayers, but better ordered than bilayers in the gel phase.