Edentulism, the absence of teeth, has evolved convergently among vertebrates, including birds, turtles, and several lineages of mammals. Instead of teeth, modern birds (Neornithes) use a horny beak (rhamphotheca) and a muscular gizzard to acquire and process food. We performed comparative genomic analyses representing lineages of nearly all extant bird orders and recovered shared, inactivating mutations within genes expressed in both the enamel and dentin of teeth of other vertebrate species, indicating that the common ancestor of modern birds lacked mineralized teeth. We estimate that tooth loss, or at least the loss of enamel caps that provide the outer layer of mineralized teeth, occurred about 116 million years ago.