The world is facing an enormous and growing threat from the emergence of bacteria that are resistant to almost all available antibiotics. Multidrug resistance is a significant public health issue, particularly for Gram-negative bacteria such as Pseudomonas aeruginosa, Acinetobacter baumannii, and Klebsiella pneumoniae, with virtually no novel drugs developed targeting them. As highlighted in the Infectious Diseases Society of America (IDSA)'s "Bad Bugs, No Drugs" paper and "Bad Bugs Need Drugs" campaign, the mismatch between increasing multidrug resistance and the dry antimicrobial-drug development pipeline led the IDSA to place these three bacteria on a "hit list" of top-priority dangerous MDR microorganisms. Meanwhile, polymyxins are increasingly being used as last-line therapy to treat infections caused by Gram-negative bacteria resistant to essentially all other currently available antibiotics. Discovered more than 50 years ago, polymyxin B (PMB) and colistin (polymyxin E) are secondary metabolite nonribosomal peptides from the soil bacterium Bacillus polymyxa. Early clinical use of parenteral PMB and colistin waned due to concerns over nephrotoxicity and neurotoxicity, but interest renewed since the mid-1990s due to prevalent MDR Gram-negative bacteria and lack of novel antibiotics. Even with a dearth of optimal use knowledge, polymyxins are used as last-line antibiotics for untreatable serious infections. Although resistance to polymyxins is currently relatively low, it can emerge rapidly in vitro, and the emergence of extremely drug-resistant (XDR) strains including resistance to polymyxins poses the most serious therapeutic challenges—resistance to polymyxins implies a total lack of antibiotics for life-threatening infections caused by these Gram-negative "superbugs", highlighting the urgency to develop new antibiotics. Given the generally good antimicrobial activity of naturally occurring polymyxins and relatively low resistance prevalence, substantial effort has been made to discover polymyxin analogues with improved microbiological, pharmacological, and toxicological profiles. This paper first reviews the current understanding of the mechanisms of polymyxins' microbiological activity and bacterial resistance, then reviews their synthesis, followed by a comprehensive treatise on their structure-activity relationships and the various analogues investigated. A literature search was conducted using PubMed (NLM) with keywords of polymyxin and structure-activity relationships.