Understanding the origin of novel complex traits is among the most fundamental goals in evolutionary biology. The most widely used definition of novelty in evolution assumes the absence of homology, yet where homology ends and novelty begins is increasingly difficult to parse as evo devo continuously revises our understanding of what constitutes homology. Here, we executed a case study to explore the earliest stages of innovation by examining the tibial teeth of tunneling dung beetles. Tibial teeth are a morphologically modest innovation, composed of relatively simple body wall projections and contained fully within the fore tibia, a leg segment whose own homology status is unambiguous. We first demonstrate that tibial teeth aid in multiple digging behaviors. We then show that the developmental evolution of tibial teeth was dominated by the redeployment of locally pre-existing gene networks. At the same time, we find that even at this very early stage of innovation, at least two genes that ancestrally function in embryonic patterning and thus entirely outside the spatial and temporal context of leg formation, have already become recruited to help shape the formation of tibial teeth. Our results suggest a testable model for how developmental evolution scaffolds innovation.