Conventional paint removal processes, based on application of chemicals and abrasion, are becoming inadequate for modern aircraft structures. In addition they are associated with severe environmental problems, mainly due to the production of hazardous waste. Several alternative novel techniques are being developed. However, the aspect of material property degradation due to the application of these new paint removal techniques has not been addressed adequately. The application of laser radiation (carbon dioxide and excimer), as well as plasma etching, has recently been associated with significant ductility deterioration and fatigue life extension. Residual stress measurements, roughness measurements and fractographic analysis were employed in order to rationalize the effect of these novel paint removal processes on the fatigue behavior of aluminum alloy 2024. The observed enhancement of fatigue life is attributed to the development of compressive residual stresses during paint removal processing. At low fatigue stresses, the magnitude of the residual stress correlates with the relative enhancement in fatigue life for the three processes investigated. The effect of surface roughening towards decreasing fatigue life is surpassed by the effect of residual stresses in extending fatigue life. Finally, the decrease of toughness and associated damage tolerance ability which follows the application of paint removal processes has been confirmed by fractographic measurements.