We describe an enormous Late Cretaceous fossil bird from Kazakhstan, known from a pair of edentulous mandibular rami (greater than 275 mm long), which adds significantly to our knowledge of Mesozoic avian morphological and ecological diversity. A suite of autapomorphies lead us to recognize the specimen as a new taxon. Phylogenetic analysis resolves this giant bird deep within Aves as a basal member of Ornithuromorpha. This Kazakh fossil demonstrates that large body size evolved at least once outside modern birds (Neornithes) and reveals hitherto unexpected trophic diversity within Cretaceous Aves.