Comprehensive two-dimensional gas chromatography time-of-flight mass spectrometry (GC × GC-TOFMS) combined to multivariate curve resolution-alternating least-squares (MCR-ALS) is proposed for the resolution and quantification of very complex mixtures of compounds such as polycyclic aromatic hydrocarbons (PAHs) in heavy fuel oil (HFO). Different GC × GC-TOFMS data slices acquired during the analysis of HFO samples and PAH standards were simultaneously analyzed using the MCR-ALS method to resolve the pure component elution profiles in the two chromatographic dimensions as well as their pure mass spectra. Outstandingly, retention time shifts within and between GC × GC runs were not affecting the results obtained using the proposed strategy and proper resolution of strongly coeluted compounds, baseline and background contributions was achieved. Calibration curves built up with standard samples of PAHs allowed the quantification of ten of them in HFO aromatic fractions. Relative errors in their estimated concentrations were in all cases below 6%. The obtained results were compared to those obtained by commercial software provided with GC × GC-TOFMS instruments and to Parallel Factor Analysis (PARAFAC). Inspection of these results showed improvement in terms of data fitting, elution process description, concentration relative errors and relative standard deviations.