Sensitive detection of acetone and hydrogen sulfide levels in exhaled human breath, serving as breath markers for some diseases such as diabetes and halitosis, may offer useful information for early diagnosis of these diseases. Exhaled breath analyzers using semiconductor metal oxide (SMO) gas sensors have attracted much attention because they offer low cost fabrication, miniaturization, and integration into portable devices for noninvasive medical diagnosis. However, SMO gas sensors often display cross sensitivity to interfering species. Therefore, selective real-time detection of specific disease markers is a major challenge that must be overcome to ensure reliable breath analysis. In this work, we report on highly sensitive and selective acetone and hydrogen sulfide detection achieved by sensitizing electrospun SnO2 nanofibers with reduced graphene oxide (RGO) nanosheets. SnO2 nanofibers mixed with a small amount (0.01 wt %) of RGO nanosheets exhibited sensitive response to hydrogen sulfide (Rair/Rgas = 34 at 5 ppm) at 200 °C, whereas sensitive acetone detection (Rair/Rgas = 10 at 5 ppm) was achieved by increasing the RGO loading to 5 wt % and raising the operation temperature to 350 °C. The detection limit of these sensors is predicted to be as low as 1 ppm for hydrogen sulfide and 100 ppb for acetone, respectively. These concentrations are much lower than in the exhaled breath of healthy people. This demonstrates that optimization of the RGO loading and the operation temperature of RGO-SnO2 nanocomposite gas sensors enables highly sensitive and selective detection of breath markers for the diagnosis of diabetes and halitosis.