Here we report the discovery of a small-bodied (approximately 1.8 m) predatory dinosaur from the Late Cretaceous (Maastrichtian) of Madagascar. Masiakasaurus knopfleri, gen. et sp. nov., represented by several skull elements and much of the postcranial skeleton, is unique in being the only known theropod with a highly procumbent and distinctly heterodont lower dentition. Such a derived dental morphology is otherwise unknown among dinosaurs. Numerous skeletal characteristics indicate that Masiakasaurus is a member of Abelisauroidea, an enigmatic clade of Gondwanan theropods. Previously, small-bodied abelisauroids were known only from Argentina. The occurrence of Masiakasaurus on Madagascar suggests that small-bodied abelisauroids, like their larger-bodied counterparts, were more cosmopolitan, radiating throughout much of Gondwana and paralleling the diversification of small coelurosaur theropods in Laurasia.