The Deepwater Horizon accident has brought oil contamination of deep-sea environments to worldwide attention. The risk for new deep-sea spills is not expected to decrease in the future, as political pressure mounts to access deep-water fossil reserves, and poorly tested technologies are used to access oil. This also applies to the response to oil-contamination events, with bioremediation the only (bio)technology presently available to combat deep-sea spills. Many questions about the fate of petroleum-hydrocarbons within deep-sea environments remain unanswered, as well as the main constraints limiting bioremediation under increased hydrostatic pressures and low temperatures. The microbial pathways fueling oil bioassimilation are unclear, and the mild upregulation observed for beta-oxidation-related genes in both water and sediments contrasts with the high amount of alkanes present in the spilled oil. The fate of solid alkanes (tar), hydrocarbon degradation rates and the reason why the most predominant hydrocarbonoclastic genera were not enriched at deep-sea despite being present at hydrocarbon seeps at the Gulf of Mexico have been largely overlooked. This mini-review aims at highlighting the missing information in the field, proposing a holistic approach where in situ and ex situ studies are integrated to reveal the principal mechanisms accounting for deep-sea oil bioremediation.