Carbon nanodots are a class of nanoparticles with variable structures and compositions which exhibit a range of useful optical and photochemical properties. Since nitrogen doping is commonly used to enhance the fluorescence properties of carbon nanodots, understanding how nitrogen affects their structure, electronic properties and fluorescence mechanism, is important to fully unravel their potential. Here we use a multi-technique approach to study heavily nitrogen-doped carbon dots synthetized by a simple bottom-up approach, and capable of bright and color-tunable fluorescence in the visible. These experiments reveal a new variant of optically-active carbonaceous dots, that is a nanocrystal of beta carbon nitride (beta-C3N4) capped by a disordered surface shell hosting a variety of polar functional groups. Because beta-C3N4 is a network of sp3 carbon and sp2 nitrogen atoms, such a structure markedly contrast with the prevailing view of carbon nanodots as sp2-carbon materials. The fluorescence mechanism of these nanoparticles is thoroughly analyzed and attributed to electronic transitions within a manifold of surface states associated to nitrogen-related groups. The sizeable bandgap of the beta-C3N4 nanocrystalline core has an indirect, albeit important role in favoring an efficient emission. These results have deep implications on our current understanding of optically-active carbon-based nanoparticles and reveal the role of nitrogen in controlling their properties.