To date, the longevity of plastic litter at the sea floor is poorly constrained. The present study compares colonization and biodegradation of plastic bags by aerobic and anaerobic benthic microbes in temperate fine-grained organic-rich marine sediments. Samples of polyethylene and biodegradable plastic carrier bags were incubated in natural oxic and anoxic sediments from Eckernförde Bay (Western Baltic Sea) for 98 days. Analyses included (1) microbial colonization rates on the bags, (2) examination of the surface structure, wettability, and chemistry, and (3) mass loss of the samples during incubation. On average, biodegradable plastic bags were colonized five times higher by aerobic and eight times higher by anaerobic microbes than polyethylene bags. Both types of bags showed no sign of biodegradation during this study. Therefore, marine sediment in temperate coastal zones may represent a long-term sink for plastic litter and also supposedly compostable material.