Comprehensive two-dimensional gas chromatography (GCxGC) coupled with a time-of-flight (ToF) detector allows the separation of many constituents of previously unresolved complex mixtures (UCM) of contaminants in sediment samples. In addition to the powerful chromatographic resolution, automated mass spectral deconvolution and identification system software enables a spectral deconvolution of closely eluting peaks. An extract of highly polluted sediment from the river Elbe (Czech Republic) was submitted to noninvasive extraction and fractionation, and analyzed by GCxGC-ToF-MS. More than 400 compounds were tentatively identified from three fractions. Some of the identified analytes, although not belonging to the group of priority pollutants, are known to have a toxic potential. Examples are chlorinated polycyclic aromatic hydrocarbons (PAHs), alkylated PAHs, quinones, aminoquinones, dinaphthofurans, and thiaarenes. Due to the lack of a more thorough cleanup, the life-span of the GC-column is substantially reduced, whereas the ion source of the MS needs more frequent maintenance. The procedure described is, however, not meant for routine purposes. This procedure delivers, in one run, a wealth of information that may be useful for further elucidation of toxicological properties of sediment samples by a tentative identification of previously unknown compounds.