We report a novel two-step method for the fabrication of high-density nanocrystalline diamond (NCD) fibers with lengths of 50–100 µm and diameters of 1–5 µm. This method includes the synthesis of templates (silica (a-SiO2) nanofibers) by a conventional vapor–liquid–solid method and the conformal coating of the nanofibers with 15–20 nm sized NCD grains by a microwave plasma enhanced chemical vapor deposition technique in hydrogen-deficient conditions. A detailed microstructural analysis was performed to probe the interaction of the NCD grains with a-SiO2 nanofibers. The specimen for transmission electron microscopy (TEM) was prepared using the focused ion beam lift-out method. Elemental line profiles across the core−sheath region of the fiber were probed by energy-dispersive X-ray microanalysis in scanning TEM mode. Room temperature micro-Raman (Ar+ laser, 514 nm excitation wavelength, with a power of 25 mW) and parallel acquisition electron energy loss spectroscopy analysis were performed to study the crystalline quality of the NCD fiber. These novel materials may find applications in micro- and nanoelectromechanical systems and as heat sinks in microelectronics.