The increasing antibiotic resistance in bacteria is an alarming phenomenon all around the world. Certain strains have developed resistance against multiple antimicrobial molecules, in which cases, the final option is to use a last-resort drug. These drugs, however, are last-resort for a reason: they can pose serious risk on vital organ functions in the patient. To mitigate the risk of severe side-effects and to reduce the rate of bacterial mutation, co-administration with other molecules that increase their efficacy seems to be the only suitable option. This leads to a reduced dose while maintaining the same level of antibiotic activity within the body. In this study, the effect of heparin derivatives on the antibiotic activity of colistin and their interactions were studied by ion mobility, mass spectrometry, and bacterium growth assays. The results show that during the association of colistin and heparin, they retain their structure while higher-stoichiometry complexes can form. When long-chain heparin is co-administered, multiple colistin molecules can associate with it, which increases the antibiotic activity by ~40% relative to the sole administration of colistin.