Cycloclasticus bacteria are ubiquitous in oil-rich regions of the ocean and are known for their ability to degrade polycyclic aromatic hydrocarbons (PAHs). In this study, we describe Cycloclasticus that have established a symbiosis with Bathymodiolus heckerae mussels and poecilosclerid sponges from asphalt-rich, deep-sea oil seeps at Campeche Knolls in the southern Gulf of Mexico. Genomic and transcriptomic analyses revealed that, in contrast to all previously known Cycloclasticus, the symbiotic Cycloclasticus appears to lack the genes needed for PAH degradation. Instead, these symbionts use propane and other short-chain alkanes such as ethane and butane as carbon and energy sources, thus expanding the limited range of substrates known to power chemosynthetic symbioses. Analyses of short-chain alkanes in the environment of the Campeche Knolls symbioses revealed that these are present at high concentrations (in the μM to mM range). Comparative genomic analyses revealed high similarities between the genes used by the symbiotic Cycloclasticus to degrade short-chain alkanes and those of free-living Cycloclasticus that bloomed during the Deepwater Horizon oil spill. Our results indicate that the metabolic versatility of bacteria within the Cycloclasticus clade is higher than previously assumed, and highlight the expanded role of these keystone species in the degradation of marine hydrocarbons.