In this work, multi-walled carbon nanotube composites (MWCNCs) were produced by catalytic pyrolysis of post-consumer plastics with aluminium oxide-supported nickel, cobalt, and their bimetallic (Ni/α–Al2O3, Co/α–Al2O3, and NiCo/α–Al2O3) oxide-based catalysts. The influence of catalyst composition and catalytic reaction temperature on the carbon yield and structure of CNCs were investigated. Different temperatures (800, 900, 950, and 1000 °C) and catalyst compositions (Ni, Co, and Ni/Co) were explored to maximize the yield of carbon deposited on the catalyst. The obtained results showed that at the same catalytic temperature (900 °C), a Ni/Co bimetallic catalyst exhibited higher carbon yield than the individual monometallic catalysts due to a better cracking capability on carbon-hydrogen bonds. With the increase of temperature, the carbon yield of the Ni/Co bimetallic catalyst increased first and then decreased. At a temperature of 950 °C, the Ni/Co bimetallic catalyst achieved its largest carbon yield, which can reach 255 mg g−1plastic. The growth of CNCs followed a “particle-wire-tube” mechanism for all studied catalysts. This work finds the potential application of complex oxide composite material catalysts for the generation of CNCs in catalytic pyrolysis of wasted plastic.