Despite being known from every continent, the geological record of pterosaurs, the first group of vertebrates to develop powered flight, is very uneven, with only a few deposits accounting for the vast majority of specimens and almost half of the taxonomic diversity. Among the regions that stand out for the greatest gaps of knowledge regarding these flying reptiles, is the Afro-Arabian continent, which has yielded only a small number of very fragmentary and incomplete materials. Here we fill part of that gap and report on the most complete pterosaur recovered from this continent, more specifically from the Late Cretaceous (similar to 95 mya) Hjoula Lagerstatte of Lebanon. This deposit is known since the Middle Ages for the exquisitely preserved fishes and invertebrates, but not for tetrapods, which are exceedingly rare. Mimodactylus libanensis gen. et sp. nov. differs from the other Afro-Arabian pterosaur species named to date and is closely related to the Chinese species Haopterus gracilis, forming a new clade of derived toothed pterosaurs. Mimodactylidae clade nov. groups species that are related to Istiodactylidae, jointly designated as Istiodactyliformes (clade nov.). Istiodactyliforms were previously documented only in Early Cretaceous sites from Europe and Asia, with Mimodactylus libanensis the first record in Gondwana.