Although the diminutive Homo floresiensis has been known for a decade, its phylogenetic status remains highly contentious. A broad range of potential explanations for the evolution of this species has been explored. One view is that H. floresiensis is derived from Asian Homo erectus that arrived on Flores and subsequently evolved a smaller body size, perhaps to survive the constrained resources they faced in a new island environment. Fossil remains of H. erectus, well known from Java, have not yet been discovered on Flores. The second hypothesis is that H. floresiensis is directly descended from an early Homo lineage with roots in Africa, such as Homo habilis; the third is that it is Homo sapiens with pathology. We use parsimony and Bayesian phylogenetic methods to test these hypotheses. Our phylogenetic data build upon those characters previously presented in support of these hypotheses by broadening the range of traits to include the crania, mandibles, dentition, and postcrania of Homo and Australopithecus. The new data and analyses support the hypothesis that H. floresiensis is an early Homo lineage: H. floresiensis is sister either to H. habilis alone or to a clade consisting of at least H. habilis, H. erectus, Homo ergaster, and H. sapiens. A close phylogenetic relationship between H. floresiensis and H. erectus or H. sapiens can be rejected; furthermore, most of the traits separating H. floresiensis from H. sapiens are not readily attributable to pathology (e.g., Down syndrome). The results suggest H. floresiensis is a long-surviving relict of an early (>1.75 Ma) hominin lineage and a hitherto unknown migration out of Africa, and not a recent derivative of either H. erectus or H. sapiens.