The emergence and growth of bacterial resistance to antibiotics poses an enormous threat to humanity in the future. In this regard, the discovery of new antibiotics and the improvement of existing ones is a priority task. In this study, we proposed the synthesis of new polymeric conjugates of polymyxin B, which is a clinically approved but limited-use peptide antibiotic. In particular, three carboxylate-bearing polymers and one synthetic glycopolymer were selected for conjugation with polymyxin B (PMX B), namely, poly(α,L-glutamic acid) (PGlu), copolymer of L-glutamic acid and L-phenylalanine (P(Glu- co-Phe)), copolymer of N-vinyl succinamic acid and N-vinylsuccinimide (P(VSAA- co-VSI)), and poly(2-deoxy-2-methacrylamido-D-glucose) (PMAG). Unlike PGlu and PMAG, P(Glu- co-Phe) and P(VSAA- co-VSI) are amphiphilic and form nanoparticles in aqueous media. A number of conjugates with different polymyxin B loading were synthesized and characterized. In addition, the complex conjugates of PGLu or PMAG with polymyxin B and deferoxamine (siderophore) were obtained. A release of PMX B from Schiff base and amide-linked polymer conjugates was studied in model buffer media with pH 7.4 and 5.8. In both cases, a more pronounced release was observed under slightly acidic conditions. The cytotoxicity of free polymers and PMX B as well as their conjugates was examined in human embryonic kidney cells (HEK 293T cell line). All conjugates demonstrated reduced cytotoxicity compared to the free antibiotic. Finally, the antimicrobial efficacy of the conjugates against Pseudomonas aeruginosa was determined and compared. The lowest values of minimum inhibitory concentrations (MIC) were observed for polymyxin B and polymyxin B/deferoxamine conjugated with PMAG. Among the polymers tested, PMAG appears to be the most promising carrier for delivery of PMX B in conjugated form due to the good preservation of the antimicrobial properties of PMX B and the ability of controlled drug release.