The Early Cretaceous fossil record of large-bodied theropods from Asia is poor, hindering comparison of Asian predatory dinosaur faunas with those from other continents. One of the few large Asian theropod specimens from this interval is a partial skull (maxilla and dentary) from the Lianmugin Formation (?Valanginian-Albian), the holotype of Kelmayisaurus petrolicus. Most authors have either considered this specimen as an indeterminate basal tetanuran or a nomen dubium. We redescribe K. petrolicus and note that it possesses a single autapomorphy (a deep accessory groove on the lateral surface of the anterior dentary), as well as a unique combination of characters that differentiates it from other theropods, affirming its validity. A phylogenetic analysis recovers K. petrolicus as a basal carcharodontosaurid, which is supported by various features: very deep interdental plates (a carcharodontosaurid synapomorphy), fused interdental plates (present in carchardontosaurids and a limited number of other theropods), and the absence of diagnostic features of other clades of large-bodied theropods such as abelisaurids, megalosauroids, and coelurosaurs. As such, Kelmayisaurus is the second known carcharodontosaurid from Asia, and further evidence that this clade represented a global radiation of large-bodied predators during the Early-mid Cretaceous.