Hydrocarbon-containing wastes and wastewaters are produced worldwide by the activities of the oil and gas industry. Anaerobic digestion has the potential to treat these waste streams, while recovering part of its energy potential as biogas. However, hydrocarbons are toxic compounds that may inhibit the microbial processes, and particularly the methanogens. In this work, the toxicity of hexadecane (0−30 mM) towards pure cultures of hydrogenotrophic methanogens (Methanobacterium formicicum and Methanospirillum hungatei) was assessed. Significantly lower (p < 0.05) methane production rates were only verified in the incubations with more than 15 mM hexadecane and represented up to 52% and 27% inhibition for M. formicicum and M. hungatei, respectively. The results obtained point out that 50% inhibition of the methanogenic activity would likely occur at hexadecane concentrations between 5−15 mM and >30 mM for M. formicicum and M. hungatei, respectively, suggesting that toxic effects from aliphatic hydrocarbons towards hydrogenotrophic methanogens may not occur during anaerobic treatment. Hydrocarbon toxicity towards hydrogenotrophic methanogens was further assessed by incubating an anaerobic sludge with H2/CO2 in the presence of a complex mixture of hydrocarbons (provided by the addition of an oily sludge from a groundwater treatment system). Specific methanogenic activity from H2/CO2 decreased 1.2 times in the presence of the hydrocarbons, but a relatively high methane production (~30 mM) was still obtained in the assays containing the inoculum and the oily sludge (without H2/CO2), reinforcing the potential of anaerobic treatment systems for methane production from oily waste/wastewater.