Macrostomatan snakes, one of the most diverse extant clades of squamates, display an impressive arsenal of cranial features to consume a vast array of preys. In the absence of indisputable fossil representatives of this clade with well-preserved skulls, the mode and timing of these extraordinary morphological novelties remain obscure. Here, we report the discovery of Kataria anisodonta n. gen. n. sp., a macrostomatan snake recovered in the Early Palaeocene locality of Tiupampa, Bolivia. The holotype consists of a partial, minute skull that exhibits a combination of booid and caenophidian characters, being the presence of an anisodont dentition and diastema in the maxilla the most distinctive trait. Phylogenetic analysis places Kataria basal to the Caenophidia+Tropidophiidae, and represents along with bolyeriids a distinctive clade of derived macrostomatans. The discovery of Kataria highlights the morphological diversity in the maxilla among derived macrostomatans, demonstrating the relevance of maxillary transformations in the evolution of this clade. Kataria represents the oldest macrostomatan skull recovered, revealing that the diversification of macrostomatans was well under way in early Tertiary times. This record also reinforces the importance of Gondwanan territories in the history of snakes, not only in the origin of the entire group but also in the evolution of ingroup clades.