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'.