We aimed to investigate polymyxin B (PMB) resistance and its molecular mechanisms in 126 Klebsiella pneumoniae isolates from rectal swabs in Brazil. Ten isolates exhibited PMB resistance with interruption of mgrB gene by insertion sequences or missense mutations. Most of the PMB-resistant isolates harbored blaKPC-2 (n = 8) and belonged to clonal complex 258 (CC258) (n = 7). These results highlight the importance of monitoring the spread of polymyxin-resistant bacteria in hospitals, since few options remain to treat multidrug-resistant isolates.