The release of 700 million liters of oil into the Gulf of Mexico over a few months in 2010 produced dramatic changes in the microbial ecology of the water and sediment. Here, we reconstructed the genomes of 57 widespread uncultivated bacteria from post-spill deep-sea sediments, and recovered their gene expression pattern across the seafloor. These genomes comprised a common collection of bacteria that were enriched in heavily affected sediments around the wellhead. Although rare in distal sediments, some members were still detectable at sites up to 60 km away. Many of these genomes exhibited phylogenetic clustering indicative of common trait selection by the environment, and within half we identified 264 genes associated with hydrocarbon degradation. Alkane degradation ability was near ubiquitous among candidate hydrocarbon degraders, whereas just three harbored elaborate gene inventories for the degradation of alkanes and aromatic and polycyclic aromatic hydrocarbons (PAHs). Differential gene expression profiles revealed a spill-promoted microbial sulfur cycle alongside gene upregulation associated with PAH degradation. Gene expression associated with alkane degradation was widespread, although active alkane degrader identities changed along the pollution gradient. Analyses suggest that a broad metabolic capacity to respond to oil inputs exists across a large array of usually rare indigenous deep-sea bacteria.