The elementary surface excitations are studied by spin-polarized electron energy loss spectroscopy on a prototype oxide surface [an oxygen passivated Fe(001)-p(1x1) surface], where the various excitations coexist. For the first time, the surface phonons and magnons are measured simultaneously and are distinguished based on their different spin nature. The dispersion relation of all excitations is probed over the entire Brillouin zone. The different phonon modes observed in our experiment are described by means of ab initio calculations.