Background Polymyxins are antimicrobials of last resort for the treatment of carbapenem-resistant Enterobacteriaceae, but resistance in 5% to >40% isolates has been reported. We conducted a genomic survey of clinical polymyxin-resistant (PR) Klebsiella pneumoniae to determine the molecular mechanisms of PR and the role of polymyxin exposure versus transmission in PR emergence. Methods We included 88 patients with PR K. pneumoniae from 2011–2018 and collected demographic, antimicrobial exposure, and infection data. Whole-genome sequencing was performed on 388 isolates, including 164 PR isolates. Variant calling and insertion sequence detection were performed, focusing on key genes associated with PR (mgrB, crrAB, phoPQ, and pmrAB). We conducted phylogenetic analyses of key K. pneumoniae multi-locus sequence types (ST258, ST17, ST307, and ST392). Results Polymyxin exposure was documented in 53⁄88 (60%) patients prior to PR detection. Through an analysis of key PR genes, we detected 129 individual variants and 72 unique variant combinations in PR isolates. This included multiple, distinct changes in 36% of patients with serial PR isolates. Insertion sequence disruption was limited to mgrB (P < .001). Polymyxin minimum inhibitory concentrations showed stepwise increases with the number of PR genes affected (P < .001). When clusters containing PR isolates in ≥2 patients were analyzed, 10⁄14 had multiple genetic events leading to PR. Conclusions Molecular mechanisms leading to PR in clinical K. pneumoniae isolates are remarkably heterogenous, even within clusters or individual patients. Polymyxin exposure with de novo PR emergence led to PR in the majority of patients, rather than transmission. Optimizing polymyxin use should be a key strategy in stopping the spread of PR.