Mangroves are ecologically important intertidal estuarine wetlands which are disappearing worldwide. Oil spills, transport activities and industrial discharge are among the typical sources of hydrocarbon pollution in urban mangroves. In this study, an attempt was made to enrich petroleum hydrocarbon-degrading cultures (PHDC) from bulk and rhizosphere sediments of a mangrove chronically polluted with oil hydrocarbons. The evaluation of mixed cultures showed higher levels of petroleum hydrocarbon (PH) removal in systems containing mineral media (MSM) amended with petroleum as sole carbon source and inoculated with rhizosphere than in sediment PHDC. After 5 days of incubation, the final concentration of PH in flasks containing sediment PHDC was moderately lower than in the control. Flasks inoculated with rhizosphere PHDC showed a sharp decrease in PH concentration. The variance analyses indicated significant differences of PH removal among enriched cultures from bulk and rhizosphere sediment samples (P<0.5). Different ndo genes and plasmids groups were enhanced from sediment and rhizosphere samples after culture enrichment in MSM media. PCR-SB hybridization analysis showed that the ndo genotypes nag, phn and nah and broad range plasmids belonging to incP-1 and incP-9 were enhanced in nearly all enriched cultures. Bacteria and taxon specific DGGE analyses were used to investigate the structural diversity of petroleum enriched cultures derived from rhizosphere and sediment samples. While Bacteria and Alphaproteobacteria DGGE fingerprint analyses revealed complex profiles, a rather low complexity of DGGE-ribotypes was detected for Betaproteobacteria, Actinobacteria and Pseudomonas. The rhizosphere PHDC formed mainly two clusters, which were better resolved by the second principal component analysis, detecting differences between PHDC. Some dominant ribotypes were common for all rhizosphere and sediment PHDC. The combination of conventional batch enrichment cultures and molecular analyses indicated that this environment has a latent potential to degrade petroleum hydrocarbons. Our results are relevant to help develop a phytoremediation strategy to mitigate the effect of oil pollution on urban mangrove forests and provided new insights on this complex environment, unravelling mechanisms and players in the process of hydrocarbon degradation.