Polymyxins are a class of antibiotics that were discovered in 1947 from programs searching for compounds effective in the treatment of Gram-negative infections. Produced by the Gram-positive bacterium Paenibacillus polymyxa and composed of a cyclic peptide chain with a peptide-fatty acyl tail, polymyxins exert bactericidal effects through membrane disruption. Currently, polymyxin B and colistin (polymyxin E) have been developed for clinical use, where they are reserved as "last-line" therapies for multidrug-resistant (MDR) infections. Unfortunately, the incidences of strains resistant to polymyxins have been increasing globally, and polymyxin heteroresistance has been gaining appreciation as an important clinical challenge. These phenomena, along with bacterial tolerance to this antibiotic class, constitute important contributors to polymyxin treatment failure. Here, we review polymyxins and their mechanism of action, summarize the current understanding of how polymyxin treatment fails, and discuss how the next generation of polymyxins holds promise to invigorate this antibiotic class.