Reductions in body size are increasingly being identified as a response to climate warming. Here we present evidence for a case of such body shrinkage, potentially due to malnutrition in early life. We show that an avian long-distance migrant (red knot, Calidris canutus canutus), which is experiencing globally unrivaled warming rates at its high-Arctic breeding grounds, produces smaller offspring with shorter bills during summers with early snowmelt. This has consequences half a world away at their tropical wintering grounds, where shorter-billed individuals have reduced survival rates. This is associated with these molluscivores eating fewer deeply buried bivalve prey and more shallowly buried seagrass rhizomes. We suggest that seasonal migrants can experience reduced fitness at one end of their range as a result of a changing climate at the other end.