Volatile secondary metabolites represent major and complex components of fruit flavor and odor. However, limited information about their genetic control is available. Quantitative trait loci (QTLs) affecting fruit volatile emission are usually identified by integrating genetic and metabolic data on germplasm collections or breeding materials. Proton Transfer Reaction—Time of Fligh—Mass Spectrometry (PTR-ToF-MS) is a novel fast and high sensitivity analytical method for VOC (Volatile Organic Compound) detection. Recently we effectively employed PTR-ToF-MS for studying the genetic control of ester emission in apple, although a complete methodology allowing full potential QTL investigations is still missing. In this work, for the first time, a new double clustering data mining strategy to fruit volatilome data produced by PTR-ToF-MS was applied. We used this new methodology in order to perform a QTL mapping investigation related to apple VOCs on a full-sib apple population (‘Golden Delicious’ × ‘Scarlet’) assessed during shelf-life ripening, resulting in the identification of several QTLs located on seven chromosomes and associated mainly with ethylene, estragole, carbonyl, alcohol, ester and sesquiterpene emission. Although the proposed methodology is applied to apple VOCs, potential for analogous investigations in other fruit species is discussed