Phage tail-like bacteriocins (tailocins) are bacterially-produced protein toxins that can mediate competitive interactions between co-colonizing bacteria. Both theoretical and empirical research has shown there are intransitive interactions between bacteriocin-producing, bacteriocin-sensitive, and bacteriocin-resistant populations, whereby producers outcompete sensitive, sensitive outcompete resistant, and resistant outcompete producers. These so-called ‘rock-paper-scissor’ dynamics explain how all three populations can be maintained in the same environment, without one genotype driving the others extinct. Using Pseudomonas syringae as a model system, we demonstrate that otherwise sensitive bacterial cells have the ability to survive bacteriocin exposure through a physiological mechanism. This mechanism is similar to the persister phenotype that allows cells to survive antibiotic exposure, without acquiring antibiotic resistance. We show that a significant fraction of the target cells that survive a lethal dose of tailocin did not exhibit any detectable increase in survival in subsequent exposure (i.e. they survived through a persistence-like mechanism). Tailocin persister cells were more prevelant in stationary rather than log phase cultures. Of the fraction of cells that gained detectable tailocin resistance, there was a range of resistance from complete (insensitive) to incomplete (partially sensitive). By genomic sequencing and genetic engineering we showed that a mutation in a hypothetical gene containing 8-10 transmembrane domains causes tailocin high-persistence and genes of various glycosyl transferases cause incomplete and complete tailocin resistance. Importantly, of the several classes of mutations, only those causing complete tailocin resistance compromised host fitness. This result, combined with previous research, indicates that bacteria likely utilize persistence as a means to survive bacteriocin-mediated killing without suffering the costs associated with resistance. This research provides important insight into how bacteria can escape the trap of fitness trade-offs associated with gaining de novo tailocin resistance, and expands our understanding of how sensistive bacterial populations can persist in the presence of lethal competitors.