A new method to generate large scale and highly dense nanoholes is presented in this paper. By the pulsed laser irradiation under water, the hydrogen etching is introduced to form high density nanoholes on the surfaces of AISI 4140 steel and Ti. In order to achieve higher nanohole density, laser shock peening (LSP) followed by recrystallization is used for grain refinement. It is found that the nanohole density does not increase until recrystallization of the substructures after laser shock peening. The mechanism of nanohole generation is studied in detail. This method can be also applied to generate nanoholes on other materials with hydrogen etching effect.