This work was aimed at evaluating a synthesis route based on the combination of mechanical milling and annealing of metal-carbon powder mixtures for the production of carbon-encapsulated nanoparticles of zirconium and hafnium carbides ZrC and HfC. These structures differ from those previously synthesized via this route by the high melting point and the high enthalpy of formation of the material of the particle core. During high-energy mechanical milling of the metal-amorphous carbon powder mixtures of the Zr-1.2Cam and Hf-1.2Cam compositions, nano-sized particles of carbides were synthesized, and during subsequent annealing of the products of milling at 750 °C in argon, these particles became encapsulated in graphitic shells. The graphitic shells covering the surface of the carbide particles are believed to form through decomposition of supersaturated solid solutions of carbon in the carbides forming during milling as a result of local melting/rapid solidification and generation of defects in the crystalline lattices of the carbides in the solid state under the impacts of the milling balls. This study has shown that nanoparticles of ZrC and HfC encapsulated in graphitic shells can be obtained by a simple and technologically attractive method based on high-energy mechanical milling of carbon-rich Zr-C and Hf-C mixtures.