The vacuum-tunneling magnetoresistance (VTMR) in Fe-vacuum-Gd tunnel junctions was studied as a function of the applied bias voltage. When the surface states are present, ferromagnetic-vacuum-ferromagnetic tunnel junctions exhibit a pronounced bias dependence. By operating the VTMR device at a bias corresponding to the energetic positions of highly spin-polarized surface states, the VTMR can be maximized.