Threespine stickleback fish offer a powerful system to dissect the genetic basis of morphological evolution in nature. Marine sticklebacks have repeatedly invaded and adapted to numerous freshwater environments throughout the Northern hemisphere. In response to new diets in freshwater habitats, changes in craniofacial morphology, including heritable increases in tooth number, have evolved in derived freshwater populations. Using a combination of quantitative genetics and genome resequencing, here we fine-mapped a quantitative trait locus (QTL) regulating evolved tooth gain to a cluster of ten QTL-associated single nucleotide variants, all within intron four of Bone Morphogenetic Protein 6 (Bmp6). Transgenic reporter assays revealed this intronic region contains a tooth enhancer. We induced mutations in Bmp6, revealing required roles for survival, growth, and tooth patterning. Transcriptional profiling of Bmp6 mutant dental tissues identified significant downregulation of a set of genes whose orthologs were previously shown to be expressed in quiescent mouse hair stem cells. Collectively these data support a model where mutations within a Bmp6 intronic tooth enhancer contribute to evolved tooth gain, and suggest that ancient shared genetic circuitry regulates the regeneration of diverse vertebrate epithelial appendages including mammalian hair and fish teeth.