Hemichordates are a marine group that, apart from one monospecific pelagic larval form, are represented by the vermiform enteropneusts and minute colonial tube-dwelling pterobranchs. Together with echinoderms, they comprise the clade Ambulacraria1. Despite their restricted diversity, hemichordates provide important insights into early deuterostome evolution, notably because of their pharyngeal gill slits2. Hemichordate phylogeny has long remained problematic3,4, not least because the nature of any transitional form that might serve to link the anatomically disparate enteropneusts and pterobranchs is conjectural. Hence, inter-relationships have also remained controversial. For example, pterobranchs have sometimes been compared to ancestral echinoderms1. Molecular data identify enteropneusts as paraphyletic, and harrimaniids5,6,7,8as the sister group of pterobranchs. Recent molecular phylogenies suggest that enteropneusts are probably basal within hemichordates, contrary to previous views9, but otherwise provide little guidance as to the nature of the primitive hemichordate7,8. In addition, the hemichordate fossil record is almost entirely restricted to peridermal skeletons of pterobranchs, notably graptolites10,11. Owing to their low preservational potentials, fossil enteropneusts are exceedingly rare12,13,14,15, and throw no light on either hemichordate phylogeny or the proposed harrimaniid–pterobranch transition. Here we describe an enteropneust,Spartobranchus tenuis(Walcott, 1911), from the Middle Cambrian-period (Series 3, Stage 5) Burgess Shale. It is remarkably similar to the extant harrimaniids, but differs from all known enteropneusts in that it is associated with a fibrous tube that is sometimes branched. We suggest that this is the precursor of the pterobranch periderm, and supports the hypothesis that pterobranchs are miniaturized and derived from an enteropneust-like worm5,6. It also shows that the periderm was acquired before size reduction and acquisition of feeding tentacles, and that coloniality emerged through aggregation of individuals, perhaps similar to the Cambrian rhabdopleuridFasciculitubus11. The presence of both enteropneusts and pterobranchs in Middle Cambrian strata, suggests that hemichordates originated at the onset of the Cambrian explosion.