Using the full potential linearised augmented planewave method we study the electronic and magnetic properties of the (001) and (111) surfaces of the half-metallic Heusler alloy NiMnSb from first-principles. We take into account all possible surface terminations including relaxations of these surfaces. Special attention is paid to the spin-polarization at the Fermi level which governs the spin-injection from such a metal into a semiconductor. In general, these surfaces lose the half-metallic character of the bulk NiMnSb, but for the (111) surfaces this loss is more pronounced. Although structural optimization does not change these features qualitatively, specifically for the (111) surfaces relaxations can compensate much of the spin-polarization at the Fermi surface that has been lost upon formation of the surface. ; Comment: 18 pages, 8 figures