Estuaries are sinks for various anthropogenic contaminants, such as petroleum hydrocarbons, giving rise to significant environmental concern. The demand for organisms and processes capable of degrading pollutants in a clean, effective, and less expensive process is of great importance. Phytoremedition approaches involving plant/bacteria interactions have been explored as an alternative, and halophyte vegetation has potential for use in phytoremedition of hydrocarbon contamination. Studies with plant species potentially suitable for microbe-assisted phytoremediation are widely represented in scientific literature. However, the in-depth understanding of the biological processes associated with the re-introduction of indigenous bacteria and plants and their performance in the degradation of hydrocarbons is still the limiting step for the application of these bioremediation solutions in a field context. The intent of the present review is to summarize the sources and effects of hydrocarbon contamination in estuarine environments, the strategies currently available for bioremediation (potential and limitations), and the perspectives of the use of halophyte plants in microbe-assisted phytoremediation approaches.