Theory predicts that short-term adaptation within populations depends on additive (A) genetic effects, while gene-gene interactions ‘epistasis (E)’ are important only in long-term evolution. However, few data exist on the genetic architecture of adaptive variation, and the relative importance of A versus non-additive genetic effects continues to be a central controversy of evolutionary biology after more than 70 years of debate. To examine this issue directly, we conducted hybridization experiments between two populations of wild soapberry bugs that have strongly differentiated in 100 or fewer generations following a host plant shift. Contrary to expectation, we found that between-population E and dominance (D) have appeared quickly in the evolution of new phenotypes. Rather than thousands of generations, adaptive gene differences between populations have evolved in tens. Such complex genetic variation could underlie the seemingly extreme rates of evolution that are increasingly reported in many taxa. In the case of the soapberry bug, extraordinary ecological opportunity, rather than mortality, may have created hard selection for genetic variants. Because ultimate division of populations into genetic species depends on epistatic loss of hybrid compatibility, local adaptation based on E may accelerate macro-evolutionary diversification.