High-resolution electron energy loss spectroscopy is used to investigate the initial stage of oxide formation on Al(111) and Ti(0001) surfaces. Analysis of the O/Al(111) vibrational data based on lattice dynamical slab calculations confirms underlayer formation as a precursor to oxidation. These results help account for some of the novel properties associated with oxygen chemisorption on Al(111) and Ti(0001) surfaces and also illustrate the ability of vibrational spectroscopy to provide surface structure information which complements results of other structure sensitive techniques.