Polymyxins are a class of lipopeptide anti-infective agents with potent and specific activity against Gram-negative bacteria. While toxicity concerns associated with polymyxin B and E (colistin) have historically limited their clinical application, today they are increasingly used as last-resort antibiotics given the rise of multidrug-resistant Gram-negative pathogens. The adverse side effects of polymyxins are well known, particularly as related to their nephrotoxicity. Here, we describe the synthesis and evaluation of a novel series of polymyxin analogues, aimed at reducing their nephrotoxic effects. Using a semisynthetic approach, we explored modifications of the exocyclic part of the polymyxin scaffold, namely, the terminal amino acid and lipophilic tail. By incorporating a reductively labile disulfide linkage in the lipid tail, we obtained novel polymyxins that exhibit potent antibacterial activity on par with polymyxin B but with reduced toxicity toward human renal proximal tubular epithelial cells.