Pn phases are observed along many refraction seismic profiles and are common in earthquake records. Their velocities usually range from 7.8 to 8.2 km s-1. Classical ray theory used to interpret these observations implies a positive upper mantle velocity gradient. However, a wide spread positive velocity gradient in the lithospheric mantle is not expected from petrological and petrophysical data. Laboratory velocity measurements at elevated temperatures and pressures suggest positive velocity gradients only for very low heat flow values (≤40 mW m-2). Higher heat flow causes negative gradients. Consequently, petrological models of the upper mantle would restrict Pn observations to Precambrian shields and old platforms, contrary to observations. We overcome this contradiction by considering media that contain random velocity fluctuations superimposed on positive or negative velocity gradients. In both cases, these structures generate Pn phases by wide-angle scattered waves. Short-wavelength random velocity fluctuations of only 0.5--1% superimposed on negative velocity gradients are sufficient for generating Pn phases. Consequently, this implies that an observed Pn wave does not necessitate a positive upper mantle velocity gradient. For a peridotitic upper mantle, fluctuations of this size can be explained by slightly varying the relative proportions of its mineralogical constituents. Anisotropy is likely to contribute to the inferred fluctuations.