The variability of two fitness–related phenotypic traits (body weight and a mandibular skeletal ratio) was analysed among cohorts and age–classes of red deer in Norway. Phenotypic variation among cohorts was pronounced for calves, yearlings and reproductively mature adults. Fluctuations in cohort–specific mean body weights and skeletal ratios of adults correlated with global climatic variation in winter conditions influenced by the North Atlantic Oscillation while cohorts were in utero. Red deer born following warm winters were smaller than those born after cold winters, and this inter–cohort variability persisted into adulthood. Phenotypic variation among cohorts of red deer influenced by climate change may pose consequences for fitness of cohorts since body size and condition contribute to reproductive success and survival in male and female red deer. In particular, the recent trend of increasingly warm winters in northern Europe and Scandinavia may lead to reduced body size and fecundity of red deer, and perhaps other ungulates, in those areas.