Teeth and denticles belong to a specialized class of mineralizing epithelial appendages called odontodes. Although homology of oral teeth in jawed vertebrates is well supported, the evolutionary origin of teeth and their relationship with other odontode types is less clear. We compared the cellular and molecular mechanisms directing development of teeth and skin denticles in sharks, where both odontode types are retained. We show that teeth and denticles are deeply homologous developmental modules with equivalent underlying odontode gene regulatory networks (GRNs). Notably, the expression of the epithelial progenitor and stem cell marker sex-determining region Y-related box 2 (sox2) was tooth-specific and this correlates with notable differences in odontode regenerative ability. Whereas shark teeth retain the ancestral gnathostome character of continuous successional regeneration, new denticles arise only asynchronously with growth or after wounding. Sox2+ putative stem cells associated with the shark dental lamina (DL) emerge from a field of epithelial progenitors shared with anteriormost taste buds, before establishing within slow-cycling cell niches at the (i) superficial taste/tooth junction (T/TJ), and (ii) deep successional lamina (SL) where tooth regeneration initiates. Furthermore, during regeneration, cells from the superficial T/TJ migrate into the SL and contribute to new teeth, demonstrating persistent contribution of taste-associated progenitors to tooth regeneration in vivo. This data suggests a trajectory for tooth evolution involving cooption of the odontode GRN from nonregenerating denticles by sox2+ progenitors native to the oral taste epithelium, facilitating the evolution of a novel regenerative module of odontodes in the mouth of early jawed vertebrates: the teeth.