Coastal environments worldwide are threatened by the effects of pollution, a risk particularly high in semienclosed basins like the Mediterranean Sea that is poorly studied from bioremediation potential perspective especially in the Southern coast. Here, we investigated the physical, chemical, and microbiological features of hydrocarbon and heavy metals contaminated sediments collected at El-Max bay (Egypt). Molecular and statistical approaches assessing the structure of the sediment-dwelling bacterial communities showed correlations between the composition of bacterial assemblages and the associated environmental parameters. Fifty strains were isolated on mineral media supplemented by 1% crude oil and identified as a diverse range of hydrocarbon-degrading bacteria involved in different successional stages of biodegradation. We screened the collection for biotechnological potential studying biosurfactant production, biofilm formation, and the capability to utilize different hydrocarbons. Some strains were able to grow on multiple hydrocarbons as unique carbon source and presented biosurfactant-like activities and/or capacity to form biofilm and owned genes involved in different detoxification/degradation processes. El-Max sediments represent a promising reservoir of novel bacterial strains adapted to high hydrocarbon contamination loads. The potential of the strains for exploitation for in situ intervention to combat pollution in coastal areas is discussed.