This article explores consensus structure elucidation on the basis of GC/EI-MS, structure generation, and calculated properties for unknown compounds. Candidate structures were generated using the molecular formula and substructure information obtained from GC/EI-MS spectra. Calculated properties were then used to score candidates according to a consensus approach, rather than filtering or exclusion. Two mass spectral match calculations (MOLGEN-MS and MetFrag), retention behavior (Lee retention index/boiling point correlation, NIST Kovat’s retention index), octanol–water partitioning behavior (log K_ow), and finally steric energy calculations were used to select candidates. A simple consensus scoring function was developed and tested on two unknown spectra detected in a mutagenic subfraction of a water sample from the Elbe River using GC/EI-MS. The top candidates proposed using the consensus scoring technique were purchased and confirmed analytically using GC/EI-MS and LC/MS/MS. Although the compounds identified were not responsible for the sample mutagenicity, the structure-generation-based identification for GC/EI-MS using calculated properties and consensus scoring was demonstrated to be applicable to real-world unknowns and suggests that the development of a similar strategy for multidimensional high-resolution MS could improve the outcomes of environmental and metabolomics studies.