The driving factors of survival, a key demographic process, have been particularly challenging to study, especially for winter migratory species such as the Adélie penguin (Pygoscelis adeliae). While winter environmental conditions clearly influence Antarctic seabird survival, it has been unclear what environmental features they are most likely to respond to. Here we examine the influence of environmental fluctuations, broad climatic conditions and the success of the breeding season prior to winter on annual survival of an Adélie penguin population using mark-recapture models based on penguin tag and resight data over a sixteen year period. This analysis required an extension to the basic Cormack-Jolly-Seber model by incorporating age structure in recapture and survival sub-models. By including model covariates we show that survival of older penguins is primarily related to the amount and concentration of ice present in their winter foraging grounds. In contrast, fledgling and yearling survival depended on other factors in addition to the physical marine environment and outcomes of the previous breeding season but we were unable to determine what these were. The relationship between sea-ice and survival differed with penguin age: extensive ice during the return journey to breeding colonies was detrimental to survival for the younger penguins whereas either too little or too much ice (between 15 and 80% cover) in the winter foraging grounds was detrimental for adults. Our results demonstrate that predictions of Adélie penguin survival can be improved by taking into account penguin age, prior breeding conditions and environmental features.