A versatile method is explored to decorate vertically aligned multi-walled carbon nanotubes (VACNTs) with NiO nanostructures. Multi-walled VACNTs are grown by plasma-enhanced chemical vapor deposition and coated with NiO nanoparticles (NPs) by drop casting. After that, the system is submitted to nanosecond pulsed UV laser irradiation in atmospheric environment. Laser irradiation provokes rapid heating-melting-cooling processes which lead to the recrystallization of NiO NPs on the outer walls of VACNTs. In this way, and depending on the laser fluence and the number of accumulated pulses, different nano-architectures such as continuous NiO coatings and spiny features on VACNTs are obtained. High-resolution scanning and transmission electron microscopies and Raman spectroscopy, corroborated with photothermal simulations, suggest that the grown nanostructures are mainly created by the laser-induced high temperatures (photothermal mechanisms). However, the observed reconstruction of the outer graphitic shells of VACNTs point to the catalytic action of NiO NPs, probably induced by the direct action of laser radiation.