The role of microorganisms in the cycling of sedimentary organic carbon is a crucial one. To better understand relationships between molecular composition of a potentially bioavailable fraction of organic matter and microbial populations, bacterial and archaeal communities were characterized using pyrosequencing-based 16S rRNA gene analysis in surface (top 30 cm) and subsurface/deeper sediments (30–530 cm) of the Helgoland mud area, North Sea. Fourier Transform Ion Cyclotron Resonance Mass Spectrometry (FT-ICR MS) was used to characterize a potentially bioavailable organic matter fraction (hot-water extractable organic matter, WE-OM). Algal polymer-associated microbial populations such as members of the Gammaproteobacteria, Bacteroidetes, and Verrucomicrobia were dominant in surface sediments while members of the Chloroflexi (Dehalococcoidales and candidate order GIF9) and Miscellaneous Crenarchaeota Groups (MCG), both of which are linked to degradation of more recalcitrant, aromatic compounds and detrital proteins, were dominant in subsurface sediments. Microbial populations dominant in subsurface sediments (Chloroflexi, members of MCG, and Thermoplasmata) showed strong correlations to total organic carbon (TOC) content. Changes of WE-OM with sediment depth reveal molecular transformations from oxygen-rich [high oxygen to carbon (O/C), low hydrogen to carbon (H/C) ratios] aromatic compounds and highly unsaturated compounds toward compounds with lower O/C and higher H/C ratios. The observed molecular changes were most pronounced in organic compounds containing only CHO atoms. Our data thus, highlights classes of sedimentary organic compounds that may serve as microbial energy sources in methanic marine subsurface environments.