This paper utilized L-alanine aminopeptidase activity as a useful approach to distinguish between Gram-negative and Gram-positive bacteria. This was done using two enzyme substrates, specifically 2-amino-N-phenylpropanamide and 2-amino-N-(4-methylphenyl)propanamide which liberated the volatile compounds aniline and p-toluidine, respectively. Two complementary analytical techniques have been used to identify and quantify the VOCs, specifically static headspace multicapillary column gas chromatography ion mobility spectrometry (SHS-MCC-GC-IMS) and headspace solid phase microextraction gas chromatography mass spectrometry (HS-SPME-GC-MS). Superior limits of detection were obtained using HS-SPME-GC-MS, typically by a factor of x6 such that the LOD for aniline was 0.02 μg/mL and 0.01 μg/mL for p-toluidine. In addition, it was also possible to determine indole interference-free by HS-SPME-GC-MS at an LOD of 0.01 μg/mL. The approach was applied to a range of selected bacteria: 15 Gram-negative and 7 Gram-positive bacteria. Use of pattern recognition, in the form of Principal Component Analysis, confirmed that it is possible to differentiate between Gram-positive and Gram-negative bacteria using the enzyme generated VOCs, aniline and p-toluidine. The exception was Stenotrophomonas maltophilia which showed negligible VOC concentrations for both aniline and p-toluidine, irrespective of the analytical techniques used and hence was not characteristic of the other Gram-negative bacteria investigated. The developed methodology has the potential to be applied for clinical and food applications.