The frog Tyrrellbatrachus brinkmani, gen. et sp. nov., is described on the basis of seven incomplete maxillae from vertebrate microfossil localities in the Upper Cretaceous (Campanian) Dinosaur Park Formation, in the Dinosaur Provincial Park area, southeastern Alberta, Canada. The maxillae are distinctive in a unique suite of features related to size, shape, and proportions of the bone, texture of the labial surface, form of the surface for inferred contact with the squamosal, form of the lamina horizontalis and the processus pterygoideus, relative depth of the crista dentalis, and in being edentulous (i.e., lacking teeth). The higher level affinities of Tyrrellbatrachus are uncertain, although certain features exclude it from several known families; for example, the presence of a processus pterygoideus excludes it from Gobiatidae (Late Cretaceous, Asia), whereas the presence of a crista dentalis and of a relatively unreduced pars facialis exclude it from Pipidae (Cretaceous–Recent, Africa and South America). The lack of teeth in Tyrrellbatrachus is notable because although tooth loss is widespread among extant anurans and has arisen independently multiple times, it has rarely been documented among Mesozoic anurans. Comparisons with the only other edentulous anuran from the Mesozoic of the Northern Hemisphere, namely Theatonius (late Campanian – late Maastrichtian, western USA), reveal no compelling similarities to support a close relationship between the two genera. Those taxa represent an early (Campanian) instance of independent tooth loss in anurans and, potentially, the oldest record of tooth loss in nonpipid anurans.