Over half of the organic carbon on Earth’s surface is trapped in marine sediment as methane hydrates. Ocean warming causes hydrate dissociation and methane leakage to the water column, rendering the characterization of microbes from hydrate depositions a pressing matter. Through genomic, phylogenetic, and biochemical assays, we characterize the first microorganisms isolated from the Rio Grande Cone (Brazil), reservoir responsible for massive methane releases to the water column. From sediment harboring rich benthic communities, we obtained 43 strains of Brevibacillus sp., Paenibacillus sp. and groups of Bacillus sp. Methane-enriched samples yielded strains of the Pseudomonas fluorescens complex, exhibiting fluorescent siderophore production and broad multi-carbon catabolism. Genomic characterization of a novel Pseudomonas sp. strain indicated 32 genes not identified in the closest related type-species, including mercury resistance proteins. Our results provide phylogenetic and genomic insights on the first bacterial isolates retrieved from a poorly explored region of the South Atlantic Ocean.