The surface proteins hemagglutinin (HA) and neuraminidase (NA) of human influenza A virus evolve under selection pressures to escape adaptive immune responses and antiviral drug treatments. In addition to these external selection pressures, some mutations in HA are known to affect the adaptive landscape of NA, and vice versa, because these two proteins are physiologically interlinked. However, the extent to which evolution of one protein affects the evolution of the other one is unknown. Here we develop a novel phylogenetic method for detecting the signatures of such genetic interactions between mutations in different genes – that is, inter-gene epistasis. Using this method, we show that influenza surface proteins evolve in a coordinated way, with mutations in HA affecting subsequent spread of mutations in NA and vice versa, at many sites. Of particular interest is our finding that the oseltamivir-resistance mutations in NA in subtype H1N1 were likely facilitated by prior mutations in HA. Our results illustrate that the adaptive landscape of a viral protein is remarkably sensitive to its genomic context and, more generally, that the evolution of any single protein must be understood within the context of the entire evolving genome. © 2015 Neverov et al.