Mutagenicity is one of the numerous adverse properties of a compound that hampers its potential to become a marketable drug. Toxic properties can often be related to chemical structure, more specifically, to particular substructures, which are generally identified as toxicophores. A number of toxicophores have already been identified in the literature. This study aims at increasing the current degree of reliability and accuracy of mutagenicity predictions by identifying novel toxicophores from the application of new criteria for toxicophore rule derivation and validation to a considerably sized mutagenicity dataset. For this purpose, a dataset of 4337 molecular structures with corresponding Ames test data (2401 mutagens and 1936 nonmutagens) was constructed. An initial substructure-search of this dataset showed that most mutagens were detected by applying only eight general toxicophores. From these eight, more specific toxicophores were derived and approved by employing chemical and mechanistic knowledge in combination with statistical criteria. A final set of 29 toxicophores containing new substructures was assembled that could classify the mutagenicity of the investigated dataset with a total classification error of 18%. Furthermore, mutagenicity predictions of an independent validation set of 535 compounds were performed with an error percentage of 15%. Since these error percentages approach the average interlaboratory reproducibility error of Ames tests, which is 15%, it was concluded that these toxicophores can be applied to risk assessment processes and can guide the design of chemical libraries for hit and lead optimization.