Background: The fossil record reveals surprising crocodile diversity in the Neogene of Africa, but relationships with their living relatives and the biogeographic origins of the modern African crocodylian fauna are poorly understood. A Plio-Pleistocene crocodile from Olduvai Gorge, Tanzania, represents a new extinct species and shows that high crocodylian diversity in Africa persisted after the Miocene. It had prominent triangular "horns" over the ears and a relatively deep snout, these resemble those of the recently extinct Malagasy crocodile Voay robustus, but the new species lacks features found among osteolaemines and shares derived similarities with living species of Crocodylus. Methodology/Principal Findings: The holotype consists of a partial skull and skeleton and was collected on the surface between two tuffs dated to approximately 1.84 million years (Ma), in the same interval near the type localities for the hominids Homo habilis and Australopithecus boisei. It was compared with previously-collected material from Olduvai Gorge referable to the same species. Phylogenetic analysis places the new form within or adjacent to crown Crocodylus. Conclusions/Significance: The new crocodile species was the largest predator encountered by our ancestors at Olduvai Gorge, as indicated by hominid specimens preserving crocodile bite marks from these sites. The new species also reinforces the emerging view of high crocodylian diversity throughout the Neogene, and it represents one of the few extinct species referable to crown genus Crocodylus.