This study investigates whether the recently described Cambrian fossil Haikouella (and the very similar Yunnanozoon) throws light on the longstanding problem of the origin of craniates. In the first rigorous cladistic analysis of the relations of this animal, we took 40 anatomical characters from Haikouella and other taxa (hemichordates, tunicates, cephalochordates, conodont craniates and other craniates, plus protostomes as the outgroup) and subjected these characters to parsimony analysis. The characters included several previously unrecognized traits of Haikouella, such as upper lips resembling those of larval lampreys, the thick nature of the branchial bars, a mandibular branchial artery but no mandibular branchial bar, muscle fibers defining the myomeres, a dark fibrous sheath that defines the notochord, conclusive evidence for paired eyes, and a large hindbrain and diencephalon in the same positions as in the craniate brain. The cladistic analysis produced this tree: (protostomes, hemichordates (tunicates, (cephalochordates, (Haikouella, (conodonts + other craniates))))), with the "Haikouella + craniate" clade supported by bootstrap values that ranged from 81-96%, depending on how the analysis was structured. Thus, Haikouella is concluded to be the sister group of the craniates. Alternate hypotheses that unite Haikouella with hemichordates or cephalochordates, or consider it a basal deuterostome, received little or no support. Although it is the sister group of craniates, Haikouella is skull-less and lacks an ear, but it does have neural-crest derivatives in its branchial bars. Its craniate characters occur mostly in the head and pharynx; its widely spaced, robust branchial bars indicate it ventilated with branchiomeric muscles, not cilia. Despite its craniate mode of ventilation, Haikouella was not a predator but a suspension feeder, as shown by its cephalochordate-like endostyle, and tentacles forming a screen across the mouth. Haikouella was compared to pre-craniates predicted by recent models of craniate evolution and was found to fit these predictions closely. Specifically, it fits Northcutt and Gans' prediction that the change from ciliary to muscular ventilation preceded the change from suspension feeding to predatory feeding; it fits Butler's claim that vision was the first craniate sense to start elaborating; it is consistent with the ideas of Donoghue and others about the ancestor of conodont craniates; and, most strikingly, it resembles Mallatt's prediction of the external appearance of the ancestral craniate head. By contrast, Haikouella does not fit the widespread belief that ancestral craniates resembled hagfishes, because it has no special hagfish characters. Overall, Haikouella agrees so closely with recent predictions about pre-craniates that we conclude that the difficult problem of craniate origins is nearly solved.