Estimating the time since discharge of spent cartridges can be a valuable tool in the forensic investigation of firearm-related crimes. To reach this aim, it was previously proposed that the decrease of volatile organic compounds released during discharge is monitored over time using non-destructive headspace extraction techniques. While promising results were obtained for large-calibre cartridges (e.g., shotgun shells), handgun calibres yielded unsatisfying results. In addition to the natural complexity of the specimen itself, these can also be attributed to some selective choices in the methods development. Thus, the present series of papers aimed to systematically evaluate the potential of headspace analysis to estimate the time since discharge of cartridges through the use of more comprehensive analytical and interpretative techniques. Following the comprehensive optimisation and validation of an exhaustive headspace sorptive extraction (HSSE) method in the first part of this work, the present paper addresses the application of chemometric tools in order to systematically evaluate the potential of applying headspace analysis to estimate the time since discharge of 9 mm Geco cartridges. Several multivariate regression and pre-treatment methods were tested and compared to univariate models based on non-linear regression. Random forests (RF) and partial least squares (PLS) proceeded by pairwise log-ratios normalisation (PLR) showed the best results, and allowed to estimate time since discharge up to 48 h of ageing and to differentiate recently fired from older cartridges (e.g., less than 5 h compared to more than 1–2 days). The proposed multivariate approaches showed significant improvement compared to univariate models. The effects of storage conditions were also tested and results demonstrated that temperature, humidity and cartridge position should be taken into account when estimating the time since discharge.