A wide ranging scientific interest in developing new and simple preparation methods for highly catalytic bimetallic sulfides provided our motivation to explore the possibility of using the pulsed electrodeposition technique for the decoration of a carbon nanotubes forest. The carbon nanotubes were obtained using the hot-filament chemical vapor deposition technique. A non-thermal plasma treatment enabled the controlled creation of defects on the carbon nanotubes’ surface. These defects served as anchoring sites for the subsequent deposition of Fe and Zn nanoparticles using the pulsed electrodeposition technique. Our findings showed that only in the case of Fe deposition prior to Zn provided the formation of FeZn bimetallic-based nanoparticles, with Zn present mainly on the outer surface of the Fe core. To induce sulfurization, a thermal treatment in sulfur vapor was conducted at 500 °C, and the obtained heterostructure consisted of Fe0.3Zn0.7S as the main phase, with the minor presence of ZnS and S residues, which was deduced from the XRD results. This study provides thorough imaging of the process, presenting for each preparation step SEM/HR-TEM findings, coupled with EDS chemical analyses. The samples were tested for photocatalytic degradation of methyl blue dye to demonstrate the photoactive behavior of the heterostructure.