Secondary edentulism (toothlessness) has evolved on multiple occasions in amniotes including several mammalian lineages (pangolins, anteaters, baleen whales), birds, and turtles. All edentulous amniote clades have evolved from ancestors with enamel-capped teeth. Previous studies have documented the molecular decay of tooth-specific genes in edentulous mammals, all of which lost their teeth in the Cenozoic, and birds, which lost their teeth in the Cretaceous. By contrast with mammals and birds, tooth loss in turtles occurred in the Jurassic (201.6-145.5 Ma), providing an extended time window for tooth gene degradation in this clade. The release of the painted turtle and Chinese softshell turtle genomes provides an opportunity to recover the decayed remains of tooth-specific genes in Testudines. We queried available genomes of Testudines (Chrysemys picta [painted turtle], Pelodiscus sinensis [Chinese softshell turtle]), Aves (Anas platyrhynchos [duck], Gallus gallus [chicken], Meleagris gallopavo [turkey], Melopsittacus undulatus [budgerigar], Taeniopygia guttata [zebra finch]), and enamelless mammals (Orycteropus afer [aardvark], Choloepus hoffmanni [Hoffmann's two-toed sloth], Dasypus novemcinctus [nine-banded armadillo]) for remnants of three enamel matrix protein (EMP) genes with putative enamel-specific functions. Remnants of the AMBN and ENAM genes were recovered in Chrysemys and retain their original synteny. Remnants of AMEL were recovered in both testudines, although there are no shared frameshifts. We also show that there are inactivated copies of AMBN, AMEL and ENAM in representatives of divergent avian lineages including Galloanserae, Passeriformes, and Psittaciformes, and that there are shared frameshift mutations in all three genes that predate the basal split in Neognathae. Among enamelless mammals, all three EMP genes exhibit inactivating mutations in Orycteropus and Choloepus. Our results highlight the power of combining fossil and genomic evidence to decipher macroevolutionary transitions and characterize the functional range of different loci involved in tooth development. The fossil record and phylogenetics combine to predict the occurrence of molecular fossils of tooth-specific genes in the genomes of edentulous amniotes, and in every case these molecular fossils have been discovered. The widespread occurrence of EMP pseudogenes in turtles, birds, and edentulous/enamelless mammals also provides compelling evidence that in amniotes, the only unique, non-redundant function of these genes is in enamel formation.