In the last decades, the encapsulation of antibiotics into nanoparticulate carriers has gained increasing attention for the treatment of infectious diseases. Sodium colistimethate-loaded solid lipid nanoparticles (Colist-SLNs) and nanostructured lipid carriers (Colist-NLCs) were designed aiming to treat the pulmonary infection associated to cystic fibrosis patients. The nanoparticles were freeze-dried using trehalose as cryoprotectant. The stability of both nanoparticles was analysed over one year according to the International Conference of Harmonisation (ICH) guidelines by determining the minimum inhibitory concentration (MIC) against clinically isolated Pseudomonas aeruginosa strains and by studying their physico-chemical characteristics. The results showed that Colist-SLNs lost their antimicrobial activity at the third month; on the contrary, the antibacterial activity of Colist-NLCs was maintained throughout the study within an adequate range (MIC ≤16 μg/mL). In addition, Colist-NLCs exhibited suitable physico-chemical properties at 5 °C and 25 °C/60% relative humidity over one year. Altogether, Colist-NLCs proved to have better stability than Colist-SLNs.