A major increase of bacterial resistance to colistin, a last-resort treatment for severe infections, was observed globally. Using colistin in livestock rearing is believed to be the ground of mobilized colistin resistance ( mcr) gene circulation and is of crucial concern to public health. This study aimed to determine the frequency and virulence characteristics of colistin-resistant Gram-negative bacteria from the milk of mastitic cows and raw unpasteurized milk in Egypt. One hundred and seventeen strains belonging to Enterobacteriaceae ( n = 90), Pseudomonas aeruginosa ( n = 10), and Aeromonas hydrophila ( n = 17) were screened for colistin resistance by antimicrobial susceptibility testing. The genetic characteristics of colistin-resistant strains were investigated for mcr- 1–9 genes, phylogenetic groups, and virulence genes. Moreover, we evaluated four commonly used biocides in dairy farms for teat disinfection toward colistin-resistant strains. Multidrug-resistant (MDR) and extensive drug-resistant (XDR) phenotypes were detected in 82.91% (97/117) and 3.42% (4/117) of the isolates, respectively. Of the 117 tested isolates, 61 (52.14%) were colistin resistant (MIC >2 mg/L), distributed as 24/70 (34.29%) from clinical mastitis, 10/11 (90.91%) from subclinical mastitis, and 27/36 (75%) from raw milk. Of these 61 colistin-resistant isolates, 47 (19 from clinical mastitis, 8 from subclinical mastitis, and 20 from raw milk) harbored plasmid-borne mcr genes. The mcr-1 gene was identified in 31.91%, mcr-2 in 29.79%, mcr-3 in 34.04%, and each of mcr-4 and mcr-7 in 2.13% of the colistin-resistant isolates. Among these isolates, 42.55% (20/47) were E. coli, 21.28% (10/47) A. hydrophila, 19.12% (9/47) K. pneumoniae, and 17.02% (8/47) P. aeruginosa. This is the first report of mcr-3 and mcr-7 in P. aeruginosa. Conjugation experiments using the broth-mating technique showed successful transfer of colistin resistance to E. coli J53-recipient strain. Different combinations of virulence genes were observed among colistin-resistant isolates with almost all isolates harboring genes. Hydrogen peroxide has the best efficiency against all bacterial isolates even at a low concentration (10%). In conclusion, the dissemination of mobile colistin resistance mcr gene and its variants between MDR- and XDR-virulent Gram-negative isolates from dairy cattle confirms the spread of mcr genes at all levels; animals, humans, and environmental, and heralds the penetration of the last-resort antimicrobial against MDR bacteria. Consequently, a decision to ban colistin in food animals is urgently required to fight XDR and MDR bacteria.