Methanogenic crude oil degradation is a significant process in subsurface environments and degradation of crude oil n-alkanes has been well documented. However, little is known about the biodegradability of the resulting heavy oil. In this study, a methanogenic consortium enriched from Shengli oilfield generated 1.3–1.9 mmol CH4/g of heavy oil at a rate of 2.9–8.8 μmol CH4/g of oil/day. Four SARA fractions (saturates, aromatics, resins and asphaltenes) of oils experienced a loss in linear aliphatic structures. n-Alkylcyclohexanes, methyl-n-alkylcyclohexanes, n-alkyldecalins, n-alkylbenzenes, n-alkyltoluenes and n-alkylxylenes with alkyl side chains longer than 14 carbons were degraded over 50% compared to the undegraded oil. In addition, the extent of degradation of these hydrocarbons increased with increasing carbon length. Correspondingly, n-fatty acids and naphthenic acids with 1–3 naphthenic rings accumulated over time. 16S rRNA gene analysis revealed that aceticlastic Methanosarcina and Methanothrix dominated in the archaeal domain, and bacterial members related to Dehalococcoidia and Soehngenia were consistently present in the successive transfer cultures. However, neither assA/masD-like genes nor alkyl-substituted succinate metabolites were detected, indicating an alternative degradation pathway, rather than addition to fumarate. This study provides novel insights into methanogenic degradation of long-chain alkyl substituted hydrocarbons in heavy oil, which also extends our understanding of anaerobic degradation of crude oil in subsurface sedimentary environments.