A major challenge to understanding the genetic basis of complex behavioral evolution is the quantification of complex behaviors themselves. Deer mice of the genus Peromyscus vary in their burrowing behavior, which leaves behind a physical trace that is easily preserved and measured. Moreover, natural burrowing behaviors are recapitulated in the lab, and there is a strong heritable component. Here we discuss potential mechanisms driving variation in burrows with an emphasis on two sister species: P. maniculatus, which digs a simple, short burrow, and P. polionotus, which digs a long burrow with a complex architecture. A forward-genetic cross between these two species identified several genomic regions associated with burrow traits, suggesting this complex behavior has evolved in a modular fashion. Because burrow differences are most likely due to differences in behavioral circuits, Peromyscus burrowing offers an exciting opportunity to link genetic variation between natural populations to evolutionary changes in neural circuits.