The cationic biopolymer ε-polylysine (ε-PL) is a potent food-grade antimicrobial that is highly effective against a range of food pathogens and spoilage organisms. In compositionally complex systems such as foods and beverages, cationic ε-PL molecules may associate with anionic substances, leading to increased turbidity, sediment formation, and reduced antimicrobial activity. This study therefore characterized the interactions between cationic ε-PL and anionic pectins with different degrees of esterification (DE) and then investigated the influence of these interactions on the antimicrobial efficacy of ε-PL. The nature of the interactions was characterized using isothermal titration calorimetry (ITC), microelectrophoresis (ME), and turbidity measurements. High (DE 61%), medium (DE 51%), and low (DE 42%) methoxyl pectins interacted with ε-PL molecules through electrostatic forces, forming either soluble or insoluble complexes with various electrical charges, depending on the relative mass ratio of pectin and ε-PL. The interaction of pectin with ε-PL increased as the negative charge density on the pectin molecules increased, that is, with decreasing DE. The antimicrobial efficacy of ε-PL against two acid-resistant spoilage yeasts (Zygosaccharomyces bailii and Saccharomyces cerevisiae) decreased progressively in the presence of increasing levels of all three pectins. Nevertheless, the low DE pectin decreased the antimicrobial efficacy of ε-PL much more dramatically, likely due to strong electrostatic binding of ε-PL onto low DE pectin molecules reducing its interaction with anionic microbe surfaces. This study provides knowledge that will facilitate the rational application of ε-PL as an antimicrobial in complex food systems.