Adaptation is a central focus of biology, although it can be difficult to identify both the strength and agent of selection and the underlying molecular mechanisms causing change. We studied cryptically colored deer mice living on the Nebraska Sand Hills and show that their light coloration stems from a novel banding pattern on individual hairs produced by an increase in Agouti expression caused by a cis-acting mutation (or mutations), which either is or is closely linked to a single amino acid deletion in Agouti that appears to be under selection. Furthermore, our data suggest that this derived Agouti allele arose de novo after the formation of the Sand Hills. These findings reveal one means by which genetic, developmental, and evolutionary mechanisms can drive rapid adaptation under ecological pressure.