Deuterostomes comprise vertebrates, the related invertebrate chordates (tunicates and cephalochordates) and three other invertebrate taxa: hemichordates, echinoderms and Xenoturbella. The relationships between invertebrate and vertebrate deuterostomes are clearly important for understanding our own distant origins. Recent phylogenetic studies of chordate classes and a sea urchin have indicated that urochordates might be the closest invertebrate sister group of vertebrates, rather than cephalochordates, as traditionally believed. More remarkable is the suggestion that cephalochordates are closer to echinoderms than to vertebrates and urochordates, meaning that chordates are paraphyletic. To study the relationships among all deuterostome groups, we have assembled an alignment of more than 35,000 homologous amino acids, including new data from a hemichordate, starfish and Xenoturbella. We have also sequenced the mitochondrial genome of Xenoturbella. We support the clades Olfactores (urochordates and vertebrates) and Ambulacraria (hemichordates and echinoderms). Analyses using our new data, however, do not support a cephalochordate and echinoderm grouping and we conclude that chordates are monophyletic. Finally, nuclear and mitochondrial data place Xenoturbella as the sister group of the two ambulacrarian phyla. As such, Xenoturbella is shown to be an independent phylum, Xenoturbellida, bringing the number of living deuterostome phyla to four.