Our understanding of how animals evolve adaptive behaviors has seen many advances in recent years, but the genetic basis for many of these behaviors remains largely unknown. Here, we assay burrowing behaviors of seven captive-bred species of deer mice (genus Peromyscus) in standardized environments. Several, but not all, species burrow even after many generations of captive breeding, and behaviors seen in the controlled lab environment resemble those seen in wild deer mice. Together these results suggest that there is a strong genetic component to burrowing in this genus. We estimated the phylogeny for these seven species using characters from mtDNA and nuclear loci. Mapping burrowing behavior onto this phylogeny reveals not only that closely related species often differ in behavior, but also that a number of morphological and behavioral traits are strongly correlated within this genus. The full spectrum of behavioral variation seen across the tree (from small, simple burrows to long, multitunnel burrows with defined entrance and exit) suggests an evolutionary sequence for increases in complexity. In particular, the complex burrows of one species, P. polionotus, appear to reflect the accumulation of adaptive genetic change over time. The interfertility of this species with its sister species, P. maniculatus, which has less complex burrows, suggests that this species pair is ideally suited for mapping the genes producing interspecific differences in burrowing behavior.