Cigarette smoking is the leading cause of preventable morbidity and mortality. Genetic variation contributes to initiation, regular smoking, nicotine dependence, and cessation. We present a Fagerström Test for Nicotine Dependence (FTND)-based genome-wide association study in 58,000 European or African ancestry smokers. We observe five genome-wide significant loci, including previously unreported loci MAGI2/GNAI1 (rs2714700) and TENM2 (rs1862416), and extend loci reported for other smoking traits to nicotine dependence. Using the heaviness of smoking index from UK Biobank (N = 33,791), rs2714700 is consistently associated; rs1862416 is not associated, likely reflecting nicotine dependence features not captured by the heaviness of smoking index. Both variants influence nearby gene expression (rs2714700/MAGI2-AS3 in hippocampus; rs1862416/TENM2 in lung), and expression of genes spanning nicotine dependence-associated variants is enriched in cerebellum. Nicotine dependence (SNP-based heritability = 8.6%) is genetically correlated with 18 other smoking traits (r = 0.40-1.09) and co-morbidities. Our results highlight nicotine dependence-specific loci, emphasizing the FTND as a composite phenotype that expands genetic knowledge of smoking.