The realization of spin-polarized vacuum tunneling is demonstrated for the Gd(0001) surface, which is ideally suited, since it exhibits a surface state that is exchange-split into two parts with opposite spin polarization. Both appear as distinct features in the tunneling spectra. The use of ferromagnetic probe tips leads to magnetic-field-dependent asymmetries in the differential tunneling conductivity at bias voltages which correspond to the energies of the spin components. By mapping the asymmetry parameter we can image the magnetic domain structure of the sample. The spin polarization of the differential tunneling conductivity is found to be in excellent agreement with (inverse) photoemission data.