Reclamation of petroleum-polluted environments is a key issue for today and in the future, as our reliance on oil will persist for decades. An eco-friendly solution is to use microbes that play a role in petroleum-hydrocarbon degradation. However, as hydrocarbon degradation involves a multi-step process involving different functional groups, focusing only on finding efficient bacterial species will not be the complete solution. Heterotrophic protists are unicellular eukaryotic microorganisms that could play a role in remediation of ecosystems by enhancing petroleum-hydrocarbon degradation through different mechanisms. This mini-review discusses the importance of protists in the degradation of petroleum-hydrocarbon and their predatory impact on hydrocarbon-degrading bacterial communities. Additionally, the effect of hydrocarbons on protistan community structure and protistan cells is discussed. A better understanding of the puzzle hydrocarbon-protist interactions will significantly increase our knowledge of how to employ these microbes for bioremediation of hydrocarbon pollutants.