This study presents the results of surface decontamination using a pulsed 150 W Nd:YAG laser (pulse width 105–230 ns, wave length 1064 nm)for the removal of epoxy paint surfaces with varying laser fluence and pulse duration. The ablation thresholds for metal and paint were determined to optimize process selectivity and the influence of laser fluence on removal rates was investigated. Modifications of the surface and grain structure of the steel substrates were characterized using a laser scanning microscope and SEM. Increased laser fluence leads to faster removal rates, while short pulses minimize changes of the metals grain structure. To simulate surface contamination, important radionuclides for decommissioning, such as Co-60, Cs-137 and Sr-90, were substituted using their stable isotopes. The decontamination effect was investigated using XRF-analysis before and after laser treatment. The results indicate that optimized laser processing parameters lead to a high decontamination factor.