Here we report the oil degradation genetic potential of six oil-degrading bacteria (ODB), previously used as a bioremediation consortium, isolated from the hydrocoral Millepora alcicornis and seawater. The strains were identified as Halomonas sp. (LC_1), Cobetia sp. (LC_6), Pseudoalteromonas shioyasakiensis (LC_2), Halopseudomonas aestusnigri (LC_3), Shewanella algae (LC_4), and Brucella intermedia (LC_5). The taxonomic identification differed from that of the original paper when we used whole genome gene markers instead of just 16S rRNA gene. Genes responsible for the degradation of aromatic hydrocarbons and n-alkanes were found in all genomes, although different (and complementary) steps of the metabolic pathways were unique to each strain. Genes for naphthalene and toluene degradation were found in various strains. We annotated quinate degradation genes in LC_6, while LC_3 and LC_5 presented genes for biosurfactant and rhamnolipid biosynthesis. We also annotated genes related to beneficial mechanisms for corals, such as genes involved in nitrogen and DMSP metabolism, cobalamin biosynthesis and antimicrobial compounds production. Our findings reinforce the importance of using bacterial consortia for bioremediation approaches instead of single strains, due to their complementary genomic arsenals. We also propose a genome-based framework to select complementary ODB that can provide additional benefits to coral health.