Colistin is a widespread last resort antibiotic for treatment of multidrug-resistant bacteria. The recent worldwide emergence of colistin resistance (Col-R) conferred by mcr-1 in human pathogens has raised concern, but the putative sources and reservoirs of novel mcr genes in the marine environment remain underexplored. We observed a high prevalence of Col-R, particularly in Vibrio isolated from European coastal waters by using the same cohorts of oysters as bioaccumulators in three sites across Europe. The high sequence diversity found in the mcr/eptA gene family was geographically structured, particularly for three novel eptA gene variants, which were restricted to the Mediterranean (France, Spain) and occurred as a dgkA-eptA operon. The RstA/RstB two component system was shown to control both the dgkA-eptA operon and the Col-R phenotype. The analysis of 29 427 Vibrionaceae genomes revealed that this mechanism of intrinsic resistance is prevalent and specific to the Harveyi clade, which includes the human pathogens Vibrio parahaemolyticus and Vibrio alginolyticus. The operon conferred colistin-resistance when transferred to sensitive non-Vibrio strains. In general, eptA gene variants are widespread and evolved with the Vibrio lineage. They occur in clade-specific genomic environments, suggesting that eptA expression responds to distinct environmental signals across the Vibrio phylogeny. However, we also identified mobile eptA paralogues that have been recently transferred between and within Vibrio clades. This highlights Vibrio as a potential source of Col-R mechanisms, emphasizing the need for enhanced surveillance to prevent colistin-resistant infections in coastal areas.