Nanoscale quantum probes such as the nitrogen-vacancy (NV) center in diamonds have demonstrated remarkable sensing capabilities over the past decade as control over fabrication and manipulation of these systems has evolved. The biocompatibility and rich surface chemistry of diamonds has added to the utility of these probes but, as the size of these nanoscale systems is reduced, the surface chemistry of diamond begins to impact the quantum properties of the NV center. In this work, we systematically study the effect of the diamond surface chemistry on the quantum coherence of the NV center in nanodiamonds (NDs) 50 nm in size. Our results show that a borane-reduced diamond surface can on average double the spin relaxation time of individual NV centers in nanodiamonds when compared to thermally oxidized surfaces. Using a combination of infrared and X-ray absorption spectroscopy techniques, we correlate the changes in quantum relaxation rates with the conversion of sp2 carbon to C–O and C–H bonds on the diamond surface. These findings implicate double-bonded carbon species as a dominant source of spin noise for near surface NV centers. The link between the surface chemistry and quantum coherence indicates that through tailored engineering of the surface, the quantum properties and magnetic sensitivity of these nanoscale systems may approach that observed in bulk diamond.