Optically active solid-state spin defects have the potential to become a versatile resource for quantum information processing applications. Nitrogen-vacancy defect centers (NV) in diamond act as quantum memories and can be interfaced by coherent photons as demonstrated in entanglement protocols. However, in particular in diamond nanostructures, the effect of spectral diffusion leads to optical decoherence hindering entanglement generation. In this work, we present strategies to significantly reduce the electric noise in diamond nanostructures. We demonstrate single NVs in nanopillars exhibiting lifetime-limited linewidth on the time scale of one second and long-term spectral stability with inhomogeneous linewidth as low as 150 MHz over three minutes. Excitation power and energy-dependent measurements in combination with nanoscopic Monte Carlo simulations contribute to a better understanding of the impact of bulk and surface defects on the NV’s spectral properties. Finally, we propose an entanglement protocol for nanostructure-coupled NVs providing entanglement generation rates up to hundreds of kHz.