We report the discovery of basal abelisaurid and carcharodontosaurid theropods from the mid Cretaceous (Aptian—Albian, ca. 112 Ma) Elrhaz Formation of the Niger Republic. The abelisaurid, Kryptops palaios gen. et sp. nov., is represented by a single individual preserving the maxilla, pelvic girdle, vertebrae and ribs. Several features, including a maxilla textured externally by impressed vascular grooves and a narrow antorbital fossa, clearly place Kryptops palaios within Abelisauridae as its oldest known member. The carcharodontosaurid, Eocarcharia dinops gen. et sp. nov., is represented by several cranial bones and isolated teeth. Phylogenetic analysis places it as a basal carcharodontosaurid, similar to Acrocanthosaurus and less derived than Carcharodontosaurus and Giganotosaurus. The discovery of these taxa suggests that large body size and many of the derived cranial features of abelisaurids and carcharodontosaurids had already evolved by the mid Cretaceous. The presence of a close relative of the North American genus Acrocanthosaurus on Africa suggests that carcharodontosaurids had already achieved a trans-Tethyan distribution by the mid Cretaceous.