Mechanical milling was employed to prepare the nanocomposite precursors for the catalytic growth of carbon nanostructures. For alumina substrates, our study showed that mechanical-millingderived catalyst precursors possessed high hydrogen reduction efficiency that in turn enabled the high yield of CNTs. The alloying effects presented by the mechanical milling could accelerate the substitutional reactions between the parent oxides and thus the quality of CNTs was apparently improved. In addition, by using water-soluble substrates such as NaCl, we realized large-scale formation of carbon-encapsulated metal nanoparticles (CEMNs) that can be completely separated by a simple washing process. It was found that the morphologies of as-obtained carbon nanostructures were strongly dependent on the substrate effects. By selecting different salt substrates, we can strategically change the morphologies of the as-obtained nanostructures, from CNTs to CEMNs and the intermediate state between CNTs and CEMNs, such as quasi-nanocages.