Atrial fibrillation (AF) is the most common cardiac arrhythmia, and it is associated with an increased risk of heart failure, stroke, dementia, and death. Recently, titin-truncating variants (TTNtv), which are predominantly associated with dilated cardiomyopathy (DCM), were associated with early-onset AF. Furthermore, genome-wide association studies (GWAS) associated AF with other structural genes. In this study, we investigated whether early-onset AF was associated with loss-of-function variants in DCM-associated genes encoding cytoskeletal proteins. Using targeted sequencing, we examined a cohort of 527 Scandinavian individuals with early-onset AF and a control group of individuals free of AF (n = 383). The patients had onset of AF before 50 years of age, normal echocardiogram, and no other cardiovascular disease at onset of AF. We identified six individuals with rare loss-of-function variants in three different genes (dystrophin (DMD), actin-associated LIM protein (PDLIM3), and fukutin (FKTN)), of which two variants were novel. Loss-of-function variants in cytoskeletal genes were significantly associated with early-onset AF when patients were compared with controls (p = 0.044). Using publicly available GWAS data, we performed genetic correlation analyses between AF and 13 other traits, e.g., showing genetic correlation between AF and non-ischemic cardiomyopathy (p = 0.0003). Our data suggest that rare loss-of-function variants in cytoskeletal genes previously associated with DCM may have a role in early-onset AF, perhaps through the development of an atrial cardiomyopathy.