Healthy participants (n = 237) aged 45-79 were tested neuropsychologically with tests of memory, speed, and cognitive control and followed up for 3-5 years (mean, 3.4 years). The sample was genotyped for apolipoprotein E (APOE) and CHolinergic Receptor for Nicotine Alpha 4 (CHRNA4), and genetic effects on cognitive function at initial testing and on cognitive decline was studied. We predicted relatively stronger effects of APOE on memory, and of CHRNA4 on speeded tasks. The predictions were partially confirmed, but we found interactive effects of APOE and CHRNA4 in several cognitive domains. Being an APOE epsilon4/CHRNA4 TT carrier was associated with slower and less efficient performance, and with steeper decline in speed tasks and in delayed recall. Age dependent genetic effects were found for both APOE and CHRNA4, where old participants (60-79 years) showed a negative influence of TT carrier status on initial memory performance, but a tendency for steeper memory decline in epsilon4 carriers. Inconsistent and small effects of APOE reported in previous studies of healthy groups may be caused by failure to consider epistasis of APOE with nicotinic receptor and other genes.