Palaeontologists assess the affinities of fossils using either morphology-based phylogenetic analyses, possibly enhanced by the use of advanced imaging techniques, or the identification of remnants or derivatives of fossil organic molecules with high taxonomic specificity (“biomarkers”). However, these approaches are often of little use for the majority of fossils whose original morphology and chemistry have been severely altered or completely lost during decay, diagenesis and modern weathering. Here we show that the inorganic incorporation of trace elements during fossilization and diagenesis can be used to assess the affinity of highly altered fossils, constituting a powerful tool overlooked so far. This is illustrated by the study of a wide range of animals from the Early Ordovician Fezouata Shale (Tremadocian, Morocco) using synchrotron X-ray fluorescence major-to-trace elemental mapping. Although all fossils studied here have turned into iron oxides, spectral analyses reveal that their different tissue types (i.e. biomineralised, sclerotised, cuticularised, and internal tissues) can be distinguished on the basis of their trace element inventories. The resulting elemental classes and distributions allowed us to identify an enigmatic, highly weathered organism as a new stem euarthropod preserving remains of its nervous system.