Antimicrobial resistance is a major concern in the dairy industry. This study investigated the prevalence, antimicrobial resistance phenotypes, and genome sequencing of Gram-negative bacteria isolated from clinical (n = 350) and subclinical (n = 95) bovine mastitis, and raw unpasteurized milk (n = 125). Klebsiella pneumoniae, Aeromonas hydrophila, Enterobacter cloacae (100% each), Escherichia coli (87.78%), and Proteus mirabilis (69.7%) were the most prevalent multidrug-resistant (MDR) species. Extensive drug-resistance (XDR) phenotype was found in P. mirabilis (30.30%) and E. coli (3.33%) isolates. Ten isolates (four E. coli, three Klebsiella species and three P. mirabilis) that displayed the highest multiple antibiotic resistance (MAR) indices (0.54–0.83), were exposed to whole-genome sequencing (WGS). Two multilocus sequence types (MLST): ST2165 and ST7624 were identified among the sequenced E. coli isolates. Three E. coli isolates (two from clinical mastitis and one from raw milk) belonging to ST2165 showed similar profile of plasmid replicon types: IncFIA, IncFIB, IncFII, and IncQ1 with an exception to an isolate that contained IncR, whereas E. coli ST7624 showed a different plasmid profile including IncHI2, IncHI2A, IncI1α, and IncFII replicon types. ResFinder findings revealed the presence of plasmid-mediated colistin mcr-10 and fosfomycin fosA5 resistance genes in a K. pneumoniae (K1) isolate from bovine milk. Sequence analysis of the reconstructed mcr-10 plasmid from WGS of K1 isolate, showed that mcr-10 gene was bracketed by xerC and insertion sequence IS26 on an IncFIB plasmid. Phylogenetic analysis revealed that K1 isolate existed in a clade including mcr-10-harboring isolates from human and environment with different STs and countries [United Kingdom (ST788), Australia (ST323), Malawi (ST2144), Myanmar (ST705), and Laos (ST2355)]. This study reports the first emergence of K. pneumoniae co-harboring mcr-10 and fosA5 genes from bovine milk in the Middle East, which constitutes a public health threat and heralds the penetration of the last-resort antibiotics. Hence, prudent use of antibiotics in both humans and animals and antimicrobial surveillance plans are urgently required.