Carbon “quantum” dots or carbon dots, generally defined as small carbon nanoparticles with various surface passivation schemes, have emerged to represent a rapidly advancing and expanding research field. A wide variety of technological applications of carbon dots have been pursued, including especially their uses as fluorescence probes or sensors. In the work reported here, carbon dots obtained from the surface chemical functionalization of small carbon nanoparticles with 2,2′-(ethylenedioxy)bis(ethylamine) (EDA) were selected as structurally compact and defined fluorescence probes, and their interactions with nitrotoluene compounds were studied on the basis of fluorescence quenching in steady-state and time-resolved measurements. The fluorescence quenching of the carbon dots by the nitrotoluenes, which are commonly used as signature compounds for nitroaromatic explosives, was found to be extremely efficient in ambient solution, though still at the very upper-limit of diffusion-control. There were some static quenching contributions at high nitrotoluene quencher concentrations, especially for the compound that is more electron deficient, which could be rationalized in terms of some near-neighbor charge transfer interactions. Mechanistic implications of the results and the potential for carbon dots to serve as highly sensitive fluorescence probes in the detection of nitroaromatic explosives are discussed.