Despite being among the most celebrated taxa from Cambrian biotas, anomalocaridids (order Radiodonta) have provoked intense debate about their affinities within the moulting-animal clade that includes Arthropoda. Current alternatives identify anomalocaridids as either stem-group euarthropods, crown-group euarthropods near the ancestry of chelicerates, or a segmented ecdysozoan lineage with convergent similarity to arthropods in appendage construction. Determining unambiguous affinities has been impeded by uncertainties about the segmental affiliation of anomalocaridid frontal appendages. These structures are variably homologized with jointed appendages of the second (deutocerebral) head segment, including antennae and 'great appendages' of Cambrian arthropods, or with the paired antenniform frontal appendages of living Onychophora and some Cambrian lobopodians. Here we describe Lyrarapax unguispinus, a new anomalocaridid from the early Cambrian Chengjiang biota, southwest China, nearly complete specimens of which preserve traces of muscles, digestive tract and brain. The traces of brain provide the first direct evidence for the segmental composition of the anomalocaridid head and its appendicular organization. Carbon-rich areas in the head resolve paired pre-protocerebral ganglia at the origin of paired frontal appendages. The ganglia connect to areas indicative of a bilateral pre-oral brain that receives projections from the eyestalk neuropils and compound retina. The dorsal, segmented brain of L. unguispinus reinforces an alliance between anomalocaridids and arthropods rather than cycloneuralians. Correspondences in brain organization between anomalocaridids and Onychophora resolve pre-protocerebral ganglia, associated with pre-ocular frontal appendages, as characters of the last common ancestor of euarthropods and onychophorans. A position of Radiodonta on the euarthropod stem-lineage implies the transformation of frontal appendages to another structure in crown-group euarthropods, with gene expression and neuroanatomy providing strong evidence that the paired, pre-oral labrum is the remnant of paired frontal appendages.