Staphylococcus aureus and cystic fibrosis (CF) are closely interlinked. To date, however, the impact of S. aureus culture in CF airways on lung function and disease progression has only been elucidated to a limited degree. This analysis aims to identify bacterial factors associated to clinical deterioration. Data were collected during an observational prospective multi-center study following 195 patients from 17 centers. The average follow-up time was 80 weeks. S. aureus isolates (n = 3180) were scanned for the presence of 25 virulence genes and agr-types using single and multiplex PCR. The presence of specific virulence genes was not associated to clinical deterioration. For the agr-types 1 and 4, however, a link to the subjects’ clinical status became evident. Furthermore, a significant longitudinal decrease in the virulence gene quantity was observed. Analyses of the plasticity of the virulence genes revealed significantly increased plasticity rates in the presence of environmental stress. The results suggest that the phylogenetic background defines S. aureus pathogenicity rather than specific virulence genes. The longitudinal loss of virulence genes most likely reflects the adaptation process directed towards a persistent and colonizing rather than infecting lifestyle.