This Letter reports on the first discrete-lattice calculation of positron surface states on the surfaces of Al. The authors reproduce the observed values and anisotropy of the binding energies on clean surfaces, and predict the surface-state lifetimes. The temperature-independent lateral diffusion constant is calculated. Monovacancies on surfaces are predicted not to trap positrons. The effect of ordered chemisorbed monolayers of oxygen is investigated: Oxidation makes the surface state unstable with respect to positronium emission.