Sites in eastern Africa have shed light on the emergence and early evolution of the genus Homo. The best known early hominin species, H. habilis and H. erectus, have often been interpreted as time-successive segments of a single anagenetic evolutionary lineage. The case for this was strengthened by the discovery of small early Pleistocene hominin crania from Dmanisi in Georgia that apparently provide evidence of morphological continuity between the two taxa. Here we describe two new cranial fossils from the Koobi Fora Formation, east of Lake Turkana in Kenya, that have bearing on the relationship between species of early Homo. A partial maxilla assigned to H. habilis reliably demonstrates that this species survived until later than previously recognized, making an anagenetic relationship with H. erectus unlikely. The discovery of a particularly small calvaria of H. erectus indicates that this taxon overlapped in size with H. habilis, and may have shown marked sexual dimorphism. The new fossils confirm the distinctiveness of H. habilis and H. erectus, independently of overall cranial size, and suggest that these two early taxa were living broadly sympatrically in the same lake basin for almost half a million years.