The emergence of antimicrobial resistance among Enterobacter spp., including resistance to extended-spectrum cephalosporins (ESC), is of great concern in both human and veterinary medicine. In this study, we investigated the prevalence of antimicrobial resistance among 60 isolates of Enterobacter spp., including E. cloacae (n = 44), E. aerogenes (n = 10), and E. asburiae (n = 6), from clinical specimens of dogs and cats from 15 prefectures in Japan. Furthermore, we characterized the resistance mechanisms harbored by these isolates, including extended-spectrum β-lactamases (ESBLs) and plasmid-mediated quinolone resistance (PMQR); and assessed the genetic relatedness of ESC-resistant Enterobacter spp. strains by multilocus sequence typing (MLST) and pulsed-field gel electrophoresis (PFGE). Antimicrobial susceptibility testing demonstrated the resistance rates to ampicillin (93.3%), amoxicillin-clavulanic acid (93.3%), cefmetazole (93.3%), chloramphenicol (46.7%), ciprofloxacin (43.3%), tetracycline (40.0%), ceftazidime (33.3%), cefotaxime (33.3%), trimethoprim/sulfamethoxazole (28.3%), gentamicin (23.3%), and meropenem (0%). Phenotypic testing detected ESBLs in 16 of 18 ESC-resistant E. cloacae isolates but not in the other species. The most frequent ESBL was CTX-M-15 (n = 8), followed by SHV-12 (n = 7), and CTX-M-3 (n = 1). As for AmpC β-lactamases, CMY-2 (n = 2) and DHA-1 (n = 2) were identified in ESC-resistant E. cloacae strains with or without ESBLs. All of the ESC-resistant E. cloacae strains also harbored one or two PMQRs, including qnrB (n = 15), aac(6')-Ib-cr (n = 8), and qnrS (n = 2). Based on MLST and PFGE analysis, E. cloacae clones of ST591-SHV-12, ST171-CTX-M-15, and ST121-CTX-M-15 were detected in one or several hospitals. These results suggested intra- and inter-hospital dissemination of E. cloacae clones co-harboring ESBLs and PMQRs among companion animals. This is the first report on the large-scale monitoring of antimicrobial-resistant isolates of Enterobacter spp. from companion animals in Japan.