Nicotine dependence is one of the world's leading causes of preventable death. To discover genetic variants that influence risk for nicotine dependence, we targeted over 300 candidate genes and analyzed 3713 single nucleotide polymorphisms (SNPs) in 1050 cases and 879 controls. The Fagerström test for nicotine dependence (FTND) was used to assess dependence, in which cases were required to have an FTND of 4 or more. The control criterion was strict: control subjects must have smoked at least 100 cigarettes in their lifetimes and had an FTND of 0 during the heaviest period of smoking. After correcting for multiple testing by controlling the false discovery rate, several cholinergic nicotinic receptor genes dominated the top signals. The strongest association was from an SNP representing CHRNB3, the β3 nicotinic receptor subunit gene (P = 9.4 × 10-5). Biologically, the most compelling evidence for a risk variant came from a non-synonymous SNP in the α5 nicotinic receptor subunit gene CHRNA5 (P = 6.4 × 10-4). This SNP exhibited evidence of a recessive mode of inheritance, resulting in individuals having a 2-fold increase in risk of developing nicotine dependence once exposed to cigarette smoking. Other genes among the top signals were KCNJ6 and GABRA4. This study represents one of the most powerful and extensive studies of nicotine dependence to date and has found novel risk loci that require confirmation by replication studies.