Colistin is a widespread last resort antibiotic for treatment of multidrug-resistant bacteria. The recent worldwide emergence of colistin resistance (Col-R) conferred bymcr-1 in human pathogens has raised concern, but the putative sources and reservoirs of novelmcrgenes in the marine environment remain underexplored. We observed a high prevalence of Col-R, particularly inVibrioisolated from European coastal waters by using a unique stock of specific-pathogen-free (SPF) oysters as a bioaccumulator. The high sequence diversity found in themcr/eptA gene family was geographically structured, particularly for three noveleptAgene variants, which were restricted to the Mediterranean (France, Spain) and occurred as adgkA-eptA operon controlled by the RstA/RstB two component system. By analyzing 29427Vibrionaceaegenome assemblies, we showed that this mechanism of intrinsic resistance is prevalent and specific to the Harveyi clade, which includes strains ofVibrio parahaemolyticusandVibrio alginolyticuscausing infections in humans. The operon conferred colistin-resistance when transferred to sensitive non-Vibriostrains. Whilemcr-andarn-based Col-R mechanisms were also identified, the widespread presence ofeptA gene variants inVibriosuggests they play a key role in intrinsic resistance to colistin. Beyond these ancienteptA gene copies having evolved with theVibriolineage, we also identified mobileeptA paralogues that have been recently transferred between and withinVibrioclades. This highlightsVibrioas a potential source of Col-R mechanisms, emphasizing the need for enhanced surveillance to prevent colistin-resistant infections in coastal areas.