PACE4 plays an important role in the progression of prostate cancer and is an attractive target for the development of novel inhibitor-based tumor therapies. We previously reported the design and synthesis of a novel, potent, and relatively selective PACE4 inhibitor known as a Multi-Leu (ML) peptide. In the present work, we examined the ML peptide through detailed structure-activity relationship studies. A variety of ML-peptide analogues modified at the P8-P5 positions with leucine isomers (Nle, DLeu, and DNle) or substituted at the P1 position with arginine mimetics were tested for their inhibitory activity, specificity, stability, and antiproliferative effect. By incorporating d isomers at the P8 position or a decarboxylated arginine mimetic, we obtained analogues with an improved stability profile and excellent antiproliferative properties. The DLeu or DNle residue also has improved specificity toward PACE4, whereas specificity was reduced for a peptide modified with the arginine mimetic, such as 4-amidinobenzylamide.