Random peptide mixtures (RPMs) have been recently proposed as powerful antimicrobial compounds. These are unique mixtures of peptides synthesized by random combination of a cationic and a hydrophobic amino acid. Here, we introduce a new type of antimicrobial compounds, short lipo-RPMs, which result from N-palmitoylation of RPMs. We report the characterization of 5-mer lipo-RPMs containing l-phenylalanine and d-lysine, named p-FdK5. p-FdK5 had high antibacterial activity against several bacterial strains and was able to reduce disease severity caused by a plant pathogen. We further synthesized and studied all 32 (25) possible lipopeptides that compose the p-FdK5 mixture. We showed that the antibacterial activity of specific lipopeptides depends on the peptide hydrophobicity and on the location of the hydrophobic amino acids relative to the palmitic acid. Interestingly, synergism assays revealed positive interactions between different sequence-specific lipopeptides in terms of antimicrobial activity.