Detrimental and beneficial interactions between co-colonizing bacteria may influence the course of infections. In cystic fibrosis (CF) airways, Staphylococcus aureus prevails in childhood, whereas Pseudomonas aeruginosa progressively predominates thereafter. While a range of interactions has been identified, it is unclear if these represent specific adaptations or correlated responses to other aspects of the environment. Here, we investigate how P. aeruginosa adapts to S. aureus by evolving P. aeruginosa in the presence and absence of S. aureus. P. aeruginosa populations that evolved for 150 generations were sequenced and compared to the ancestor strain. Mutations in the Wsp signaling system were identified in both treatments and likely occurred because of low oxygen availability. Despite showing increased killing activity, wsp mutants were less fit in the presence of S. aureus. In contrast, mutations in lipopolysaccharide (LPS) biosynthesis occurred exclusively in co-cultures with S. aureus and conferred a fitness gain in its presence. Moreover, they increased resistance towards beta-lactam antibiotics. Strikingly, both mutations in wsp and LPS genes are observed in clinical isolates from CF-patients. Our results suggest that P. aeruginosa LPS mutations are a direct consequence of S. aureus imposed selection in vitro.