Sixty percent of the patients with restless legs syndrome (RLS) report a positive family history. To date five loci have been mapped on chromosome 12q, 14q, 9p, 2q, and 20p (RLS1-5) but no gene has been identified so far. To identify genes related to RLS, we performed a three-stage association study (explorative study, replication study, high-density mapping) in two Caucasian RLS case-control samples of altogether 918 independent cases and controls. In the explorative study (367 cases and controls, respectively), we screened 1536 SNPs in 366 genes in a 21 Mb region encompassing the RLS1 critical region on chromosome 12. Armitage trend test revealed three genomic regions that were significant (P < 0.05). In the replication study (551 cases and controls, respectively) we genotyped the most significant SNPs of Stage 1. After correction for multiple testing, association was observed with SNP rs7977109 (P(nominal) = 0.00175, P(Westfall-Young) = 0.04895, OR = 0.76228, 95% CI = 0.64310-0.90355), which is in the neuronal nitric oxide synthase (NOS1) gene. High-density mapping using altogether 34 tagging and coding SNPs of the NOS1 gene in both case-control samples further confirmed the significant association results to NOS1. Ten more SNPs revealed significance with nominal P-values from 0.0001 to 0.0482 (genotypic test and Armitage test). Altogether, this study provides evidence for an association of variants in the NOS1 gene and RLS, and suggests the involvement of the NO/arginine pathway in the pathogenesis of RLS. Potential usage of NO modulating agents as new treatment options for RLS have become a challenging aspect for future research of this disorder.