Neuraminidase (NA) of human influenza H3N2 virus has evolved rapidly and been accumulating mutations for more than half-century. However, biophysical constraints that govern the evolutionary trajectories of NA remain largely elusive. Here, we show that among 70 natural mutations that are present in the NA of a recent human H3N2 strain, >10% are deleterious for an ancestral strain. By mapping the permissive mutations using combinatorial mutagenesis and next-generation sequencing, an extensive epistatic network is revealed. Biophysical and structural analyses further demonstrate that certain epistatic interactions can be explained by non-additive stability effect, which in turn modulates membrane trafficking and enzymatic activity of NA. Additionally, our results suggest that other biophysical mechanisms also contribute to epistasis in NA evolution. Overall, these findings not only provide mechanistic insights into the evolution of human influenza NA and elucidate its sequence-structure-function relationship, but also have important implications for the development of next-generation influenza vaccines.