Cuticular hydrocarbons (CHCs) form the boundary between insects and their environments and often act as essential cues for species, mate and kin recognition. This complex polygenic trait can be highly variable both among and within species, but the causes of this variation, especially the genetic basis, are largely unknown. In this study, we investigated phenotypic and genetic variation of CHCs in the seaweed fly, C. frigida, and found that composition was affected by both genetic (sex and population) and environmental (larval diet) factors. We subsequently conducted behavioral trials that show CHCs are likely used as a sexual signal. We identified general shifts in CHC chemistry as well as individual compounds and found that the methylated compounds, mean chain length, proportion of alkenes, and normalized total CHCs differed between sexes and populations. We combined this data with whole genome re-sequencing data to examine the genetic underpinnings of these differences. We identified 11 genes related to CHC synthesis and found population level outlier SNPs in 5 that are concordant with phenotypic differences. Together these results reveal that the CHC composition of C. frigida is dynamic, strongly affected by the larval environment, and likely under natural and sexual selection.