Background: Memory CD8 T cells to influenza A viruses are widely detectable in healthy human subjects and broadly crossreactive for serologically distinct influenza A virus subtypes. However, it is not clear to what extent such pre-existing cellular immunity can provide cross-subtype protection against novel emerging influenza A viruses. Methodology/Principal Findings: We show in the mouse model that naturally occurring sequence variations of the conserved nucleoprotein of the virus significantly impact cross-protection against lethal disease in vivo. When priming and challenge viruses shared identical sequences of the immunodominant, protective NP366/Db epitope, strong cross-subtype protection was observed. However, when they did not share complete sequence identity in this epitope, cross-protection was considerably reduced. Contributions of virus-specific antibodies appeared to be minimal under these circumstances. Detailed analysis revealed that the magnitude of the memory CD8 T cell response triggered by the NP366/Db variants was significantly lower than those triggered by the homologous NP366/Dbligand. It appears that strict specificity of a dominant public TCR to the original NP366/Db ligand may limit the expansion of cross-reactive memory CD8 T cells to the NP366/Dbvariants. Conclusions/Significance: Pre-existing CD8 T cell immunity may provide substantial cross-protection against heterosubtypic influenza A viruses, provided that the priming and the subsequent challenge viruses share the identical sequences of the immunodominant, protective CTL epitopes.