Atrial fibrillation (AF) is the most common sustained cardiac arrhythmia in man, causing substantial morbidity and mortality with a major worldwide public health impact. It is increasingly recognized as a highly heritable condition. This study aimed to determine genetic risk factors for early-onset AF. We sequenced the whole genomes of 8453 Icelanders and imputed genotypes of the 25.5 million sequence variants we discovered into 1799 Icelanders with early-onset AF (diagnosed before 60 years of age) and 337 453 controls. Each sequence variant was tested for association based on multiplicative and recessive inheritance models. We discovered a rare frameshift deletion in the myosin MYL4 gene (c.234delC) that associates with early-onset AF under a recessive mode of inheritance (allelic frequency = 0.58%). We found eight homozygous carriers of the mutation, all of whom had early-onset AF. Six of the homozygotes were diagnosed by the age of 30 and the remaining two in their 50s. Three of the homozygotes had received pacemaker implantations due to sick sinus syndrome, three had suffered an ischemic stroke, and one suffered sudden cardiac death. Through a population approach we found a loss of function mutation in the myosin gene MYL4 that, in the homozygous state, is completely penetrant for early-onset AF. The finding may provide novel mechanistic insight into the pathophysiology of this complex arrhythmia.