Gulls are the primary hosts of H13 and H16 avian influenza viruses (AIVs). The molecular basis for this host restriction is only partially understood. In this study, amino acid sequences from Eurasian gull H13 and H16 AIVs and Eurasian AIVs (non H13 and H16) were compared to determine if specific signatures are present only in the internal proteins of H13 and H16 AIVs, using a bioinformatics approach. Amino acids identified in an initial analysis performed on 15 selected sequences were checked against a comprehensive set of AIV sequences retrieved from Genbank to verify them as H13 and H16 specific signatures. Analysis of protein similarities and prediction of subcellular localization signals were performed to search for possible functions associated with the confirmed signatures. H13 and H16 AIV specific signatures were found in all the internal proteins examined, but most were found in the non-structural protein 1 (NS1) and in the nucleoprotein. A putative functional signature was predicted to be present in the nuclear export protein. Moreover, it was predicted that the NS1 of H13 and H16 AIVs lack one of the nuclear localization signals present in NS1 of other AIV subtypes. These findings suggest that the signatures found in the internal proteins of H13 and H16 viruses are possibly related to host restriction.