Complex mixtures of polycyclic aromatic hydrocarbons (PAHs) are difficult to resolve because of the high degree of overlap in compound vapor pressures, boiling points, and mass spectral fragmentation patterns. The objective of this research was to improve the separation of complex PAH mixtures (including 97 different parent, alkyl-, nitro-, oxy-, thio-, chloro-, bromo-, and high molecular weight PAHs) using GC × GC/ToF-MS by maximizing the orthogonality of different GC column combinations and improving the separation of PAHs from the sample matrix interferences, including unresolved complex mixtures (UCM). Four different combinations of nonpolar, polar, liquid crystal, and nanostationary phase columns were tested. Each column combination was optimized and evaluated for orthogonality using a method based on conditional entropy that considers the quantitative peak distribution in the entire 2D space. Finally, an atmospheric particulate matter with diameter <2.5 μm (PM(2.5)) sample from Beijing, China, a soil sample from St. Maries Creosote Superfund Site, and a sediment sample from the Portland Harbor Superfund Site were analyzed for complex mixtures of PAHs. The highest chromatographic resolution, lowest synentropy, highest orthogonality, and lowest interference from UCM were achieved using a 10 m × 0.15 mm × 0.10 μm LC-50 liquid crystal column in the first dimension and a 1.2 m × 0.10 mm × 0.10 μm NSP-35 nanostationary phase column in the second dimension. In addition, the use of this column combination in GC × GC/ToF-MS resulted in significantly shorter analysis times (176 min) for complex PAH mixtures compared to 1D GC/MS (257 min), as well as potentially reduced sample preparation time.