Because of the increased electron density within the surface layer, metal surfaces are generally expected to have tensile surface stress. Here, using first-principles density functional calculations, we demonstrate that in magnetic 3d metals surface magnetism can alter this commonly accepted picture. We find that the thermodynamically stable surfaces of chromium and manganese possess compressive surface stress. The revealed negative surface stress is shown to be ascribed to the enhanced magnetic moments within the surface layer relative to the bulk values.