Surface proteins hemagglutinin (HA) and neuraminidase (NA) of the human influenza A virus evolve under selection pressure to escape the human adaptive immune response 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 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 substitutions in HA affecting substitutions 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, imply that the evolution of any single protein must be understood within the context of the entire evolving genome.