Due to concerns over the global increase of antibiotic-resistant bacteria, alternative antibacterial strategies, such as phage therapy, are increasingly being considered. However, evolution of bacterial resistance to new therapeutics is almost a certainty; indeed, it is possible that resistance to alternative treatments might result in an evolved trade-up such as enhanced antibiotic resistance. Here, we hypothesize that selection for Escherichia coli bacteria to resist phage T6, phage U115, or albicidin, a DNA gyrase inhibitor, should often result in a pleiotropic trade-up in the form of cross-resistance, because all three antibacterial agents interact with the Tsx porin. Selection imposed by any one of the antibacterials resulted in cross-resistance to all three of them, in each of the 29 spontaneous bacterial mutants examined in this study. Furthermore, cross-resistance did not cause measurable fitness (growth) deficiencies for any of the bacterial mutants, when competed against wild-type E. coli in both low-resource and high-resource environments. A combination of whole-genome and targeted sequencing confirmed that mutants differed from wild-type E. coli via change(s) in the tsx gene. Our results indicate that evolution of cross-resistance occurs frequently in E. coli subjected to independent selection by phage T6, phage U115 or albicidin. This study cautions that deployment of new antibacterial therapies such as phage therapy, should be preceded by a thorough investigation of evolutionary consequences of the treatment, to avoid the potential for evolved trade-ups.