The announcement of a new species, Homo floresiensis, a primitive hominin that survived until relatively recent times is an enormous challenge to paradigms of human evolution. Until this announcement, the dominant paradigm stipulated that: 1) only more derived hominins had emerged from Africa, and 2) H. sapiens was the only hominin since the demise of Homo erectus and Homo neanderthalensis. Resistance to H. floresiensis has been intense, and debate centers on two sets of competing hypotheses: 1) that it is a primitive hominin, and 2) that it is a modern human, either a pygmoid form or a pathological individual. Despite a range of analytical techniques having been applied to the question, no resolution has been reached. Here, we use cladistic analysis, a tool that has not, until now, been applied to the problem, to establish the phylogenetic position of the species. Our results produce two equally parsimonious phylogenetic trees. The first suggests that H. floresiensis is an early hominin that emerged after 'Homo rudolfensis' (1.86 Ma) but before H. habilis (1.66 Ma, or after 1.9 Ma if the earlier chronology for H. habilis is retained). The second tree indicates H. floresiensis branched after Homo habilis.