Yunnanozoans are a distinctive clade of Lower Cambrian metazoans. Although widely accepted as deuterostomes, their exact placement within this superphylum is controversial. Here we describe a new species of Haikouella (H. jianshanensis) from the Chengjiang Lagerstätte (Yunnan, China) with exceptional preservation of a number of features. These include external gills, which suggest that the origin of the pharyngeal clefts was independent of the gills. The diagnostic branchial arches of chordates may, therefore, be composite structures. No evidence was found for the chordate-like structures that have been described in other yunnanozoans. We propose that yunnanozoans are stem-group deuterostomes, allied to the vetulicolians.