Despite a rich African Plio-Pleistocene hominin fossil record, the ancestry of Homo and its relation to earlier australopithecines remain unresolved. Here we report on two partial skeletons with an age of 1.95 to 1.78 million years. The fossils were encased in cave deposits at the Malapa site in South Africa. The skeletons were found close together and are directly associated with craniodental remains. Together they represent a new species of Australopithecus that is probably descended from Australopithecus africanus. Combined craniodental and postcranial evidence demonstrates that this new species shares more derived features with early Homo than any other australopith species and thus might help reveal the ancestor of that genus.