A facile 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 and submitted to pulsed UV laser irradiation. 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 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 and catalytic action of NiO NPs.