A method of laser shock peening a metallic part by firing a laser on a coated laser shock peening surface of the part which has been covered with an explosive coating containing at least one explosive ingredient. Two or more explosive ingredients having different shock sensitivities may be used and the laser beam is fired with sufficient power to explode at least some amount of each of the explosive ingredients. One embodiment of the invention includes forming an ablative coated surface by coating a laser shock peening surface on the workpiece with an ablative material containing at least one explosive ingredient, continuously firing a laser beam which repeatably pulses between relatively constant periods, on the coated surface of the workpiece while providing continuous movement between the laser beam and the metallic workpiece, and firing the laser beam with sufficient power to vaporize the ablative material of the coating and to explode at least some of the explosive ingredient with the pulses and forming laser beam spots on the coating and forming a region in the workpiece having deep compressive residual stresses imparted by the laser beam pulsing such that the region extends into the workpiece from the laser shock peening surface. Suitable explosive ingredients include nitroglycerin and ammonium nitrate. One or more oxidizers may be added to an ablative material to form the explosive coating in the form of a tape or film coating.