Nicotine dependence is moderately heritable, but identified genetic associations explain only modest portions of this heritability. We analyzed 3369 SNPs from 349 candidate genes and investigated whether incorporation of SNP-by-environment interaction into association analyses might bolster gene discovery efforts and prediction of nicotine dependence. Specifically, we incorporated the interaction between allele count and age at onset of regular smoking (AOS) into association analyses of nicotine dependence. Subjects were from the Collaborative Genetic Study of Nicotine Dependence and included 797 cases ascertained for Fagerström nicotine dependence and 811 non-nicotine-dependent smokers as controls, all of European descent. Compared with main effect models, SNP x AOS interaction models resulted in higher numbers of nominally significant tests, increased predictive utility at individual SNPs and higher predictive utility in a multi-locus model. Some SNPs previously documented in main effect analyses exhibited improved fits in the joint analysis, including rs16969968 from CHRNA5 and rs2314379 from MAP3K4. CHRNA5 exhibited larger effects in later-onset smokers, in contrast with a previous report that suggested the opposite interaction (Weiss et al. 2008). However, a number of SNPs that did not emerge in main effect analyses were among the strongest findings in the interaction analyses. These include SNPs located in GRIN2B (P = 1.5 x 10(-5)), which encodes a subunit of the N-methyl-D-aspartate receptor channel, a key molecule in mediating age-dependent synaptic plasticity. Incorporation of logically chosen interaction parameters, such as AOS, into genetic models of substance use disorders may increase the degree of explained phenotypic variation and constitutes a promising avenue for gene discovery.