Owing to exceptional biomolecule preservation, fossil avian eggshell has been used extensively in geochronology and palaeodietary studies. Here, we show, to our knowledge, for the first time that fossil eggshell is a previously unrecognized source of ancient DNA (aDNA). We describe the successful isolation and amplification of DNA from fossil eggshell up to 19 ka old. aDNA was successfully characterized from eggshell obtained from New Zealand (extinct moa and ducks), Madagascar (extinct elephant birds) and Australia (emu and owl). Our data demonstrate excellent preservation of the nucleic acids, evidenced by retrieval of both mitochondrial and nuclear DNA from many of the samples. Using confocal microscopy and quantitative PCR, this study critically evaluates approaches to maximize DNA recovery from powdered eggshell. Our quantitative PCR experiments also demonstrate that moa eggshell has approximately 125 times lower bacterial load than bone, making it a highly suitable substrate for high-throughput sequencing approaches. Importantly, the preservation of DNA in Pleistocene eggshell from Australia and Holocene deposits from Madagascar indicates that eggshell is an excellent substrate for the long-term preservation of DNA in warmer climates. The successful recovery of DNA from this substrate has implications in a number of scientific disciplines; most notably archaeology and palaeontology, where genotypes and/or DNA-based species identifications can add significantly to our understanding of diets, environments, past biodiversity and evolutionary processes.