The emergence of colistin-resistant Pseudomonas aeruginosa in cystic fibrosis (CF) patients, particularly after long-term inhalation treatments, has been recently reported. Nanoencapsulation may enable preparations to overcome the limitations of conventional pharmaceutical forms. We have determined the time-dependent viability of P. aeruginosa biofilms treated with both free and nanoencapsulated colistin. We also examined the relationship between the optimal anti-biofilm activity of nanostructured lipid carrier (NLC)-colistin and the structural organization of the biofilm itself. The results showed the more rapid killing of P. aeruginosa bacterial biofilms by NLC-colistin than by free colistin. However, the two formulations did not differ in terms of the final percentages of living and dead cells, which were higher in the inner than in the outer layers of the treated biofilms. The effective anti-biofilm activity of NLC-colistin and its faster killing effect recommend further studies of its use over free colistin in the treatment of P. aeruginosa infections in CF patients.