Background: A public health need exists to describe the epidemiology and trends of all Staphylococcus aureus (S. aureus) infections given the emergence of USA300 methicillin-resistant S. aureus (MRSA) and changing epidemiology of MRSA infection. Also needed is a validated algorithm to identify S. aureus infections using large healthcare databases. Methods: We conducted a retrospective population-based study in veterans receiving health care in the VAMHCS from fiscal years (FY) 1999-2008. A non-invasive S. aureus infection was defined as a positive clinical culture from a non-sterile site with an ICD-9 code for infection. An invasive S. aureus infection was defined as a positive blood or clinical culture from a sterile site. Infections were classified by hospital-onset (HO: culture > 48 hrs after hospitalization) or community-onset (CO: culture while outpatient or ≤48 hrs after hospitalization), methicillin-susceptibility (MSSA or MRSA) and body site. Positive (PPV) and negative predictive values (NPV) for non-invasive infections were determined by chart review using a reference standard. Incidence was calculated per 100,000 veterans or inpatient days. Time series were analyzed using Quasi-Poisson generalized linear regression models (GLMs). Results: There were 3,674 S. aureus infections of which 77% were non-invasive and 61% due to MRSA. PPV and NPV of a clinical culture and ICD-9 were 79% (95% CI 70-86%) and 82% (95% CI 73-88) respectively. Proportion of CO and HO were 69% and 32% respectively. The averaged annual incidences were 749, 178, and 571 per 100,000 veterans for all, invasive and non-invasive infections respectively. The annual incidence significantly increased (p<0.001) due to increases in non-invasive MRSA infections (271 to 504/100,000 veterans, 1.9 fold increase) and non-invasive CO infections (360 to 546/100,000 veterans, 1.5 fold increase) of which >60% were skin and soft tissue infections (SSTIs). GLMs revealed an increased risk of all infections. Incidence of invasive S. aureus infections decreased 2.3 fold. Conclusion: Clinical culture and ICD-9 is a predictive approach to identify non-invasive S. aureusinfection. From FY1999 to 2008, the incidence of all S. aureus infections significantly increased due to increases in CO non-invasive MRSA SSTIs; however, gradual decreases in invasive S. aureus infections were observed.