The detection and level assessment of microorganisms is a practical quality/contamination indicator of food and water samples. Conventional analytical procedures (e.g., culture methods, immunological techniques, and polymerase chain reactions), while accurate and widely used, are time-consuming, costly, and generate a large amount of waste. Electronic noses (E-noses), combined with chemometrics, provide a direct, green, and non-invasive assessment of the volatile fraction without the need for sample pre-treatments. The unique olfactory fingerprint generated during each microorganism’s growth can be a vehicle for its detection using gas sensors. A lab-made E-nose, comprising metal oxide semiconductor sensors was applied, to analyze solid medium containing Gram-positive (Enterococcus faecalis and Staphylococcus aureus) or Gram-negative (Escherichia coli and Pseudomonas aeruginosa) bacteria. The electrical-resistance signals generated by the E-nose coupled with linear discriminant analysis allowed the discrimination of the four bacteria (90% of correct classifications for leave-one-out cross-validation). Furthermore, multiple linear regression models were also established allowing quantifying the number of colony-forming units (CFU) (0.9428 ≤ R2 ≤ 0.9946), with maximum root mean square errors lower than 4 CFU. Overall, the E-nose showed to be a powerful qualitative–quantitative device for bacteria preliminary analysis, being envisaged its possible application in solid food matrices.