The Ni, Ni-Mo, Ni-Mg, and Ni-Mo-Mg catalysts were systematically explored for the one-step conversion of polystyrene (PS) into carbon nanotubes (CNTs). The catalysts were characterized in the phase structure, morphology, reducibility, and carbonization performance. It was found that the Mo contributed to the small catalyst particle growth by the formation of NiMoO4 phase. The addition of Mg had no effect on catalyst particle sizes but effectively controlled the carbon solubility and led to the growth of CNTs by the generation of NiMgO2. Finally, we demonstrated that the Ni Mo Mg catalysts showed the most efficient for the conversion of PS into CNTs owing to the individually synergetic effect of Mo and Mg elements. Besides catalysts, the degradation additives and the carbonization temperature were also discussed for their effects on the carbonization of PS. It is believed that the work provides, potential for the conversion of PS waste into CNTs.