Developmental genetic studies of evolved differences in morphology have led to the hypothesis that cis-regulatory changes often underlie morphological evolution. However, because most of these studies focus on evolved loss of traits, the genetic architecture and possible association with cis-regulatory changes of gain traits are less understood. Here we show that a derived benthic freshwater stickleback population has evolved an approximate twofold gain in ventral pharyngeal tooth number compared with their ancestral marine counterparts. Comparing laboratory-reared developmental time courses of a low-toothed marine population and this high-toothed benthic population reveals that increases in tooth number and tooth plate area and decreases in tooth spacing arise at late juvenile stages. Genome-wide linkage mapping identifies largely separate sets of quantitative trait loci affecting different aspects of dental patterning. One large-effect quantitative trait locus controlling tooth number fine-maps to a genomic region containing an excellent candidate gene, Bone morphogenetic protein 6 (Bmp6). Stickleback Bmp6 is expressed in developing teeth, and no coding changes are found between the high- and low-toothed populations. However, quantitative allele-specific expression assays of Bmp6 in developing teeth in F1 hybrids show that cis-regulatory changes have elevated the relative expression level of the freshwater benthic Bmp6 allele at late, but not early, stages of stickleback development. Collectively, our data support a model where a late-acting cis-regulatory up-regulation of Bmp6 expression underlies a significant increase in tooth number in derived benthic sticklebacks.