The influenza A nucleoprotein (NP) is an attractive target for avian flu vaccine development because of its high conversancy in the evolutionary chain of the virus. Here we identified two novel HLA-A*0201 restricted NP epitopes, named H5N1 NP373-381 AMDSNTLEL (NP373) and NP458-466 FQGRGVFEL (NP458), using computational bioinformatic analysis. The NP peptides showed a high binding affinity to HLA-A*0201 on T2 cells, and were able to induce the activation of the cytotoxic T cells in the human peripheral blood mononuclear cells. We examined the potential of using NP373 and NP458 peptide sequences supplemented with a single-chain trimer as potential DNA vaccine candidates in an HHD transgenic mouse model. A gene gun delivery system was used for administrating the vaccine candidates into the animals. The results from cytotoxicity and ELISPOT assays indicated that a significant amount of IFN-γ was secreted by the T cells of the vaccinated mice, and the T cells were able to eliminate the corresponding peptide-loaded T2 cells. The discovery of these novel immunogenic NP peptides provides valuable information for avian flu vaccine design and construction.