Headspace solid-phase microextraction (HS-SPME) comprehensive two-dimensional (2D) gas chromatography combined with quadrupole-mass spectrometry (GC×GC-qMS) with dedicated comparative data elaboration was applied to separate chemical patterns arising from the interaction between some Mentha species and the herbivore Chrysolina herbacea, also known as the mint bug. Upon feeding on different Mentha species (Mentha spicata L., Mentha × piperita L. and Mentha longifolia L.), C. herbacea produced frass (faeces) which were characterized by a typical volatile fraction. HS-SPME GC×GC-qMS analysis of the complex volatile fraction of both mint leaf and C. herbacea frass was submitted to advanced fingerprinting analysis of 2D chromatographic data. 1,8-Cineole, found in the leaves of all the Mentha species examined, was oxidized, and C. herbacea frass yielded high rates of several hydroxy-1,8-cineoles, including 2α-hydroxy-, 3α-hydroxy-, 3β-hydroxy- and 9-hydroxy-1,8-cineole. Upon insect feeding, several unknown oxidized monoterpenes, a p-menthane diol and three unknown phenylpropanoids were also detected in the frass volatiles. In M. longifolia, the occurrence of the monoterpene piperitenone oxide was found to be toxic and associated with insect death. The results of this work show that high throughput techniques such as HS-SPME and GC×GC-qMS fingerprint analysis are ideal tools to analyze complex volatile matrices, and provide a sensitive method for the direct comparison and chemical visualization of plant and insect emitted volatile components.