The Hyaenidae are today a small carnivoran family including only four monospecific genera, although their paleodiversity was very high from the Miocene to the Pleistocene, with a paleobiogeographic distribution spanning Eurasia, Africa and North America. The living species Crocuta crocuta, Parahyaena brunnea and Proteles cristatus are limited to the African Continent, while the distribution of Hyaena hyaena includes northern, central and eastern Africa and southwestern Asia. The paleontological record suggests that forms very similar to the extant ones lived in Africa at least from the late Pliocene. Here we report new hyaenid craniodental material from the renowned site of Olduvai Gorge, in northern Tanzania. The fossils were found in three different Olduvai localities (FC West, MCK East and Loc. 64 in Naisiusiu area), within layers spanning stratigraphically from Bed I to Upper Bed II (Early Pleistocene). We refer the remains to Hyaena sp., Crocuta cf. ultra and Crocuta sp., supporting the occurrence of at least two hyenas (the smaller and slenderer Hyaena and the large and robust Crocuta) in the Olduvai Bed I-II carnivore guild.