Improving the therapeutic characteristics of antibiotics is an effective strategy for controlling the growth of multidrug-resistant Gram-negative microorganisms. The purpose of this study was to develop a colistin (CT) delivery system based on hyaluronic acid (HA) and the water-soluble cationic chitosan derivative, diethylaminoethyl chitosan (DEAECS). The CT delivery system was a polyelectrolyte complex (PEC) obtained by interpolymeric interactions between the HA polyanion and the DEAECS polycation, with simultaneous inclusion of positively charged CT molecules into the resulting complex. The developed PEC had a hydrodynamic diameter of 210–250 nm and a negative surface charge (ζ-potential = −19 mV); the encapsulation and loading efficiencies were 100 and 16.7%, respectively. The developed CT delivery systems were characterized by modified release (30–40% and 85–90% of CT released in 15 and 60 min, respectively) compared to pure CT (100% CT released in 15 min). In vitro experiments showed that the encapsulation of CT in polysaccharide carriers did not reduce its antimicrobial activity, as the minimum inhibitory concentrations against Pseudomonas aeruginosa of both encapsulated CT and pure CT were 1 μg/mL.