Polymyxins are peptide antibiotics that are highly efficient against many multidrug resistant pathogens. However, the poor stability of polymyxins in the bloodstream requires the administration of high drug doses that, in turn, can lead to polymyxin toxicity. Consequently, different delivery systems have been considered for polymyxins to overcome these obstacles. In this work, we report the development of polymyxin delivery systems based on nanoparticles obtained from the self-assembly of amphiphilic random poly(L-glutamic acid-co-D-phenylalanine). These P(Glu-co-DPhe) nanoparticles were characterized in terms of their size, surface charge, stability, cytotoxicity, and uptake by macrophages. The encapsulation efficiency and drug loading into P(Glu-co-DPhe) nanoparticles were determined for both polymyxin B and E. The release kinetics of polymyxins B and E from nanoformulations was studied and compared in buffer solution and human blood plasma. The release mechanisms were analyzed using a number of mathematical models. The minimal inhibitory concentrations of the nanoformulations were established and compared with those determined for the free antibiotics.