Structural coloration underpins communication strategies in many extant insects but its evolution is poorly understood. This stems, in part, from limited data on how color alters during fossilization. We resolve this by using elevated pressures and temperatures to simulate the effects of burial on structurally colored cuticles of modern beetles. Our experiments show that the color generated by multilayer reflectors changes due to alteration of the refractive index and periodicity of the cuticle layers. Three-dimensional photonic crystals are equally resistant to degradation and thus their absence in fossil insects is not a function of limited preservation potential but implies that these color-producing nanostructures evolved recently. Structural colors alter directly to black above a threshold temperature in experiments, identifying burial temperature as the primary control on their preservation in fossils. Color-producing nanostructures can, however, survive in experimentally treated and fossil cuticles that now are black. An extensive cryptic record is thus available in fossil insects to illuminate the evolution of structural color.