The acquisition of physiological strategies to tolerate novel thermal conditions allows organisms to exploit new environments. As a result, thermal tolerance is a key determinant of the global distribution of biodiversity, yet the constraints on its evolution are not well understood. Here we investigate parallel evolution of cold tolerance in New Zealand stick insects, an endemic radiation containing three montane-occurring species. Using a phylogeny constructed from 274 orthologous genes, we show that stick insects have independently colonized montane environments at least twice. We compare supercooling point and survival of internal ice formation among ten species from eight genera, and identify both freeze tolerance and freeze avoidance in separate montane lineages. Freeze tolerance is also verified in both lowland and montane populations of a single, geographically widespread, species. Transcriptome sequencing following cold shock identifies a set of structural cuticular genes that are both differentially regulated and under positive sequence selection in each species. However, while cuticular proteins in general are associated with cold shock across the phylogeny, the specific genes at play differ among species. Thus, while processes related to cuticular structure are consistently associated with adaptation for cold, this may not be the consequence of shared ancestral genetic constraints.