We investigated 17 abandoned Adélie penguin (Pygoscelis adeliae) colonies in the Windmill Islands, East Antarctica, in summer 2002/03. Forty radiocarbon dates on penguin bones and eggshells from 13 of these sites indicate a near continuous occupation by breeding penguins in this region for over 9000 years. These dates refine the recent geological record in this region and indicate that deglaciation of the northern islands occurred much earlier than previously suggested. Dietary remains from these sites include at least 23 taxa of cephalopods and teleost fish. Quantification of these remains indicates significant fluctuations in the relative abundance of two of the more common major prey taxa. The Antarctic silverfish (Pleuragramma antarcticum Boulenger) was the most common teleost prey during all time periods represented by the ages of the sites, but preservational factors may explain a gradual decrease in the remains of this species in increasingly older sites. The most common cephalopod in the sediments was the squid, Psychroteuthis glacialis Thiele, which occurred in low numbers in most sites except one (Site 75). An unusually high number of squid beaks preserved in Site 75, dating to approximately 5700–6100 cal. yr BP, does not correlate with a decrease in fish prey at that time. The high number of abandoned penguin colonies (> 200) in the Windmill Islands may be due to population cycles in the past in association with low nest-site fidelity and movement by breeding penguins to new sites within this region.