The Kem Kem beds in South Eastern Morocco contain a rich early Upper (or possibly late Lower) Cretaceous vertebrate assemblage. Fragmentary remains, predominantly teeth and jaw tips, represent several kinds of pterosaur although only one species, the ornithocheirid Coloborhynchus moroccensis, has been named. Here, we describe a new azhdarchid pterosaur, Alanqa saharica nov. gen. nov. sp., based on an almost complete well preserved mandibular symphysis from Aferdou N'Chaft. We assign additional fragmentary jaw remains, some of which have been tentatively identified as azhdarchid and pteranodontid, to this new taxon which is distinguished from other azhdarchids by a remarkably straight, elongate, lance-shaped mandibular symphysis that bears a pronounced dorsal eminence near the posterior end of its dorsal (occlusal) surface. Most remains, including the holotype, represent individuals of approximately three to four meters in wingspan, but a fragment of a large cervical vertebra, that probably also belongs to A. saharica, suggests that wingspans of six meters were achieved in this species. The Kem Kem beds have yielded the most diverse pterosaur assemblage yet reported from Africa and provide the first clear evidence for the presence of azhdarchids in Gondwana at the start of the Late Cretaceous. This, the relatively large size achieved by Alanqa, and the additional evidence of variable jaw morphology in azhdarchids provided by this taxon, indicates a longer and more complex history for this clade than previously suspected.