Trees’ total amount of nonstructural carbohydrate (NSC) stores and the proportion of these stores residing as insoluble starch are vital traits for individuals living in variable environments. However, our understanding of how stores vary in response to environmental stress is poorly understood as the genetic component of storage is rarely accounted for in studies. Here, we quantified variation in NSC traits in branch samples taken from over 600 clonally transplanted black cottonwood (Populus trichocarpa) trees grown in two common gardens. We found heritable variation in both total NSC stores and the proportion of stores in starch (H2TNC = 0.19, H2PropStarch = 0.31), indicating a substantial genetic component of variation. In addition, we found high amounts of plasticity in both traits in response to cold temperatures and significant genotype-by-environment (GxE) interactions in the total amount of NSC stored (54% of P is GxE). This finding of high GxE indicates extensive variation across trees in their response to environment, which may explain why previous studies of carbohydrate stores’ responses to stress have failed to converge on a consistent pattern. Overall, we found high amounts of environmental and genetic variation in NSC storage concentrations, which may bolster species against future climate change.