Background/Objectives: Antimicrobial resistance (AMR) in companion animals is an increasing concern within the One Health framework, particularly regarding opportunistic pathogens such as Klebsiella spp. This retrospective study evaluated the epidemiology, antimicrobial susceptibility profiles, and temporal resistance trends of Klebsiella spp. infections in dogs and cats across the Iberian Peninsula. Methods: A total of 809 clinical isolates collected between 2016 and 2024 and submitted to a private diagnostic laboratory in Barcelona were analysed. Results: Klebsiella pneumoniae was the predominant species (70%), more frequently identified in cats (76%) than in dogs (68%). Dermatological and respiratory samples exhibited the highest prevalence of multidrug-resistant (MDR) isolates. Overall MDR prevalence was high, particularly in cats (51.1%; 95% CI 41.1–60.9%) compared with dogs (38.4%; 95% CI 34.1–42.8%) although it was not statistically significant. K. pneumoniae generally exhibited higher resistance rates than K. oxytoca, particularly to amoxicillin/clavulanic acid, first-/second-generation cephalosporins, third-/fourth-generation cephalosporins (3/4th GC), fluoroquinolones, and tetracyclines. In both bacterial species, resistance rates were consistently higher among feline isolates. In contrast, aminoglycosides and phenicols retained high activity against most isolates. Temporal analysis revealed a significant increasing resistance trend to amoxicillin/clavulanic acid, which is particularly concerning given the widespread use of this antimicrobial as a first-line treatment in small animal practice. However, resistance trend to aminoglycosides showed a significant decline. No significant temporal changes were detected for 3/4th GC and fluoroquinolones, suggesting the persistence of resistant populations within companion animals. Resistance to aminoglycosides and phenicols remained comparatively low in this study. Whereas critically important category B antimicrobials, such as 3/4th GC and fluoroquinolones, exhibited low to moderate effectiveness, raising concerns about their empirical use. Conclusions: These findings highlight the substantial AMR and MDR burden of K. pneumoniae in companion animals in the Iberian Peninsula and reinforce the need for prudent antimicrobial use, routine susceptibility testing, and integrated One Health surveillance strategies.