CuZn39Pb3 leaded brass is one of the most widely used alloys in machining. Despite its good machinability, there is a lack of information in the literature on the effects of surface cold working on the surface microhardness, microhardness profile, introduced residual stresses, microstructure, and the operating behaviour of machined components. This article reveals the capabilities of conventional diamond burnishing (DB) (implemented under flood-lubrication conditions) to improve the surface integrity and high- and mega-cycle fatigue strength of CuZn39Pb3 cylindrical components such as axles and shafts. The results show that both the smoothing and hardening DB processes achieve mirror-like surfaces, introduce significant residual compressive stresses at depths greater than 0.5 mm, and significantly increase the fatigue strength in the high- and mega-cycle regions compared to the reference condition (turned and polished specimens). However, the surface microhardness is weakly affected by the degree of surface cold working. Given the almost identical microhardness profiles and the equivalent distribution in depth of the introduced residual stresses by the two DB processes, the possible reason for the more pronounced effect of the hardening process on the fatigue strength lies in the thicker affected layer and the reduced negative skewness introduced by this process.