Bacterial resistance to polymyxins, antibiotics of last resort, is increasing in frequency amongst Gram-negative pathogens due to the dissemination of mobile colistin resistance genes (mcr). These mcr genes have typically been investigated in clinical- or livestock- associated Gammaproteobacteria. Here, we report the first mcr gene initially identified outside of Gammaproteobacteria, and the first in an environmental isolate. Genome sequencing of a heavy metal resistant Pigmentiphaga litoralis isolate from coal fly ash contaminated sediment from Lake Macquarie (NSW, Australia) revealed two novel resistance plasmids (pPLE30.1, 100 kb; pPLE30.2, 199 kb). These plasmids contained metal and antibiotic resistance gene combinations, including a highly unusual cluster of a putative polymyxin resistance gene, named mcr-12, directly between arsHCB and czcCBA on pPLE30.2. Curing of pPLE30.2 reduced the resistance to polymyxin B 64-fold, in addition to reducing resistance to zinc, cobalt, cadmium, arsenate and arsenite by 4-, 2-, 2-, 32- and 32-fold, respectively. This confirms the metal and antibiotic resistance function of pPLE30.2. Reintroduction of mcr-12 on a broad host range vector restored polymyxin B resistance. Mcr-12 shared structural homology with other Mcr and EptA enzymes, however Mcr-12 had only 39.6% amino acid identity to the closest characterized homologue, thus warranting a new mcr gene number. Expression of mcr-12 led to increased polymyxin B and colistin resistance in Pseudomonadales (Pseudomonas aeruginosa, Acinetobacter baumanii, and Pseudomonas protegens) but not Enterobacterales (Klebsiella pneumoniae, Enterobacter cloacae subsp. cloacae, and uropathogenic Escherichia coli). Matrix-assisted laser desorption/ionization mass spectrometry confirmed the enzyme’s function as a phosphoethanolamine transferase. This work showcases the important link between anthropogenic heavy metal contamination and antibiotic resistance genes, and highlights the importance of One Health approaches for the understanding and management of antimicrobial resistance.