Nanotechnology-based modification of known antimicrobial agents is a rational and straightforward way to improve their safety and effectiveness. The aim of this study was to develop colistin (CT)-loaded polymeric carriers based on hyaluronic acid (HA) for potential application as antimicrobial agents against multi-resistant gram-negative microorganisms (including ESKAPE pathogens). CT-containing particles were obtained via a polyelectrolyte interaction between protonated CT amino groups and HA carboxyl groups (the CT-HA complex formation constant [logKCT-HA] was about 5.0). The resulting polyelectrolyte complexes had a size of 210–250 nm and a negative charge (ζ-potential −19 mV), with encapsulation and loading efficiencies of 100% and 20%, respectively. The developed CT delivery systems were characterized by modified release (45% and 85% of CT released in 15 and 60 min, respectively) compared to pure CT (100% CT released in 15 min). In vitro tests showed that the encapsulation of CT in polymer particles did not reduce its pharmacological activity; the minimum inhibitory concentrations of both encapsulated CT and pure CT were 1 μg/mL (against Pseudomonas aeruginosa).