The molecularly defined clade Ecdysozoa comprises the panarthropods (Euarthropoda, Onychophora and Tardigrada) and the cycloneuralian worms (Nematoda, Nematomorpha, Priapulida, Loricifera and Kinorhyncha). These disparate phyla are united by their means of moulting, but otherwise share few morphological characters--none of which has a meaningful fossilization potential. As such, the early evolutionary history of the group as a whole is largely uncharted. Here we redescribe the 508-million-year-old stem-group onychophoran Hallucigenia sparsa from the mid-Cambrian Burgess Shale. We document an elongate head with a pair of simple eyes, a terminal buccal chamber containing a radial array of sclerotized elements, and a differentiated foregut that is lined with acicular teeth. The radial elements and pharyngeal teeth resemble the sclerotized circumoral elements and pharyngeal teeth expressed in tardigrades, stem-group euarthropods and cycloneuralian worms. Phylogenetic results indicate that equivalent structures characterized the ancestral panarthropod and, seemingly, the ancestral ecdysozoan, demonstrating the deep homology of panarthropod and cycloneuralian mouthparts, and providing an anatomical synapomorphy for the ecdysozoan supergroup.