The Deepwater Horizon blowout in the Gulf of Mexico in 2010, one of the largest marine oil spills(1), changed bacterial communities in the water column and sediment as they responded to complex hydrocarbon mixtures(2-4). Shifts in community composition have been correlated to the microbial degradation and use of hydrocarbons(2,5,6), but the full genetic potential and taxon-specific metabolisms of bacterial hydrocarbon degraders remain unresolved. Here, we have reconstructed draft genomes of marine bacteria enriched from sea surface and deep plume waters of the spill that assimilate alkane and polycyclic aromatic hydrocarbons during stable-isotope probing experiments, and we identify genes of hydrocarbon degradation pathways. Alkane degradation genes were ubiquitous in the assembled genomes. Marinobacter was enriched with n-hexadecane, and uncultured Alpha- and Gammaproteobacteria populations were enriched in the polycyclic-aromatic-hydrocarbon-degrading communities and contained a broad gene set for degrading phenanthrene and naphthalene. The repertoire of polycyclic aromatic hydrocarbon use varied among different bacterial taxa and the combined capabilities of the microbial community exceeded those of its individual components, indicating that the degradation of complex hydrocarbon mixtures requires the non-redundant capabilities of a complex oil-degrading community.