The polymyxins are nonribosomal lipopeptides produced by Paenibacillus polymyxa and are potent antibiotics with activity specifically directed against Gram-negative bacteria. While the clinical use of polymyxins has historically been limited due to their toxicity, their use is on the rise given the lack of alternative treatment options for infections due to multidrug resistant Gram-negative pathogens. The Gram-negative specificity of the polymyxins is due to their ability to target lipid A, the membrane embedded LPS anchor that decorates the cell surface of Gram-negative bacteria. Notably, the mechanisms responsible for polymyxin toxicity, and in particular their nephrotoxicity, are only partially understood with most insights coming from studies carried out in the past decade. In parallel, many synthetic and semisynthetic polymyxin analogues have been developed in recent years in an attempt to mitigate the nephrotoxicity of the natural products. Despite these efforts, to date, no polymyxin analogues have gained clinical approval. This may soon change, however, as at the moment there are three novel polymyxin analogues in clinical trials. In this context, this review provides an update of the most recent insights with regard to the structure-activity relationships and nephrotoxicity of new polymyxin variants reported since 2010. We also discuss advances in the synthetic methods used to generate new polymyxin analogues, both via total synthesis and semisynthesis.