How polymorphisms are maintained within populations over long periods of time remains debated, because genetic drift and various forms of selection are expected to reduce variation. Here, we study the genetic architecture and maintenance of phenotypic morphs that confer crypsis in Timema cristinae stick insects, combining phenotypic information and genotyping-by-sequencing data from 1360 samples across 21 populations. We find two highly divergent chromosomal variants that span megabases of sequence and are associated with color polymorphism. We show that these variants exhibit strongly reduced effective recombination, are geographically widespread, and probably diverged millions of generations ago. We detect heterokaryotype excess and signs of balancing selection acting on these variants through the species’ history. A third chromosomal variant in the same genomic region likely evolved more recently from one of the two color variants and is associated with dorsal pattern polymorphism. Our results suggest that large-scale genetic variation associated with crypsis has been maintained for long periods of time by potentially complex processes of balancing selection.