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 low concentrations (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.