Between 2005 and 2007, a warming anomaly of the Atlantic water inflow into the Arctic Ocean took place in the Eastern Fram Strait. Together with a decrease in sea-ice coverage, this anomaly resulted in a decreased phytodetritus export to the deep sea. Only little is known about ecological consequences on Arctic warming on the entire ecosystem from surface to the seafloor. By annual sampling between 2003 to 2009 at the Long-Term Ecological Research (LTER) site HAUSGARTEN (79°N, 4°E; Eastern Fram Strait), we investigated how the warming and consequent variation in food supply affected benthic bacterial and eukaryotic communities, which were determined by 454 massively parallel tag sequencing. Bacterial richness decreased during the time of limited food supply, yet both abundant and rare bacterial types showed different responses in their relative abundances, resulting in a strong shift of the bacterial community structure. Also, eukaryotic richness of all size classes decreased at times of limited food supply, as did their community composition. Our results indicate a rapid reaction of the benthic community to changes in surface ocean conditions that will occur under future climate change.