Pseudomonas aeruginosa and Staphylococcus aureus frequently occur together in polymicrobial infections, and there is evidence that their interactions negatively affect disease outcome in patients. At the molecular level, interactions between the two bacterial species are well-described, with P. aeruginosa usually being the dominant species suppressing S. aureus through a variety of inhibitory molecules. However, in chronic infections the two species interact over prolonged periods of time, and S. aureus might be able to evolve resistance against inhibitory molecules deployed by P. aeruginosa. Here, we used experimental evolution to test this hypothesis by exposing three different S. aureus strains (Cowan I, 6850, and JE2) to the growth-inhibitory supernatant of P. aeruginosa PAO1 over 30 days. Prior to evolution, we found that S. aureus strains were inhibited by secreted compounds regulatorily controlled by the Pseudomonas quinolone signal quorum-sensing system. Following evolution, inhibitory effects were significantly attenuated, and we observed that adaptations were S. aureus strain specific and involved the upregulation of virulence traits such as staphyloxanthin production and the formation of small colony variants. At the genetic level, mutations in membrane transporters (known to be involved in antibacterial uptake) were the most frequent evolutionary targets. Our work indicates that adaptations of S. aureus to P. aeruginosa occurs rapidly and affect both virulence trait expression and membrane transporter functionality. Thus, pathogen evolution could promote species co-existence and complicate treatment options in infections. IMPORTANCE Polymicrobial infections are common. In chronic infections, the different pathogens may repeatedly interact, which could spur evolutionary dynamics with pathogens adapting to one another. Here, we explore the potential of Staphylococcus aureus to adapt to its competitor Pseudomonas aeruginosa. These two pathogens frequently co-occur, and P. aeruginosa is seen as the dominant species being able to displace S. aureus. We studied three different S. aureus strains and found that all became quickly resistant to inhibitory compounds secreted by P. aeruginosa. Our experimental evolution revealed strains-specific adaptations with three main factors contributing to resistance evolution: (i) overproduction of staphyloxanthin, a molecule protecting from oxidative stress; (ii) the formation of small colony variants also protecting from oxidative stress; and (iii) alterations of membrane transporters possibly reducing toxin uptake. Our results show that species interactions can change over time potentially favoring species co-existence, which in turn could affect disease progression and treatment options.