Livestock constitutes a potential reservoir of meticillin-resistant Staphylococcus aureus isolates belonging to a recently derived lineage within clonal complex 398 (MRSA CC398-IIa). Since its discovery in the early 2000s, this lineage has become a major cause of human disease in Europe, posing a serious public health challenge in countries with intensive livestock production. To retrace the history of human colonisation and infection with MRSA CC398-IIa in Denmark, we conducted a nationwide, retrospective study of MRSA isolates collected from 1999 to 2011. Among 7,429 MRSA isolates screened, we identified 416 MRSA CC398-IIa isolates. Of these, 148 were from people with infections, including 51 from patients reporting no livestock exposure. The first cases of MRSA CC398-IIa infection in Denmark occurred in 2004. Subsequently, the incidence of MRSA CC398-IIa infection showed a linear annual increase of 66% from 2004 to 2011 (from 0.09 to 1.1 per 100,000 person-years). There were clear temporal and spatial relationships between MRSA CC398-IIa-infected patients with and without livestock exposure. These findings suggest substantial dissemination of MRSA CC398-IIa from livestock or livestock workers into the Danish community and underscore the need for strategies to control its spread both on and off the farm.