Deuterostomes are a morphologically disparate clade, encompassing the chordates (including vertebrates), the hemichordates (the vermiform enteropneusts and the colonial tube-dwelling pterobranchs) and the echinoderms (including starfish). Although deuterostomes are considered monophyletic, the inter-relationships between the three clades remain highly contentious. Here we report, Yanjiahella biscarpa, a bilaterally symmetrical, solitary metazoan from the early Cambrian (Fortunian) of China with a characteristic echinoderm-like plated theca, a muscular stalk reminiscent of the hemichordates and a pair of feeding appendages. Our phylogenetic analysis indicates that Y. biscarpa is a stem-echinoderm and not only is this species the oldest and most basal echinoderm, but it also predates all known hemichordates, and is among the earliest deuterostomes. This taxon confirms that echinoderms acquired plating before pentaradial symmetry and that their history is rooted in bilateral forms. Yanjiahella biscarpa shares morphological similarities with both enteropneusts and echinoderms, indicating that the enteropneust body plan is ancestral within hemichordates.