Microorganisms exist almost exclusively in interactive multispecies communities, but genetic determinants of the fitness of interacting bacteria, and accessible adaptive pathways, remain uncharacterized. Here, using a two-species system, we studied the antagonism of Pseudomonas aeruginosa against Escherichia coli. Our unbiased genome-scale approach enabled us to identify multiple factors that explained the entire antagonism observed. We discovered both forms of ecological competition-sequestration of iron led to exploitative competition, while phenazine exposure engendered interference competition. We used laboratory evolution to discover adaptive evolutionary trajectories in our system. In the presence of P. aeruginosa toxins, E. coli populations showed parallel molecular evolution and adaptive convergence at the gene-level. The multiple resistance pathways discovered provide novel insights into mechanisms of toxin entry and activity. Our study reveals the molecular complexity of a simple two-species interaction, an important first-step in the application of systems biology to detailed molecular dissection of interactions within native microbiomes.