Novel coaxial structures consisting of nitrogen-doped carbon nanotube (MWNTs-CNx) cores with external concentric shells of pure carbon were produced by the pyrolysis of toluene over Fe-coated MWNTs-CNx. These materials were thoroughly characterized by SEM, HRTEM, X-ray diffraction, and TGA; a possible growth scenario for their formation is also proposed. In addition, these coaxial structures were able to form 2D and 3D covalent networks that mainly exhibited T-, Y-, and on-type morphologies. The two-step technique presented here could be further developed to fully control the growth of these new coaxial structures, study of individual junctions, and it could be used to create periodic nanotube networks, in which the heterocable structure could find applications in nanoelectronics.