In wild aquatic birds and poultry around the world, influenza A viruses carrying 15 antigenic subtypes of hemagglutinin (HA) and 9 antigenic subtypes of neuraminidase (NA) have been described. Here we describe a previously unidentified antigenic subtype of HA (H16), detected in viruses circulating in black-headed gulls in Sweden. In agreement with established criteria for the definition of antigenic subtypes, hemagglutination inhibition assays and immunodiffusion assays failed to detect specific reactivity between H16 and the previously described subtypes H1 to H15. Genetically, H16 HA was found to be distantly related to H13 HA, a subtype also detected exclusively in shorebirds, and the amino acid composition of the putative receptor-binding site of H13 and H16 HAs was found to be distinct from that in HA subtypes circulating in ducks and geese. The H16 viruses contained NA genes that were similar to those of other Eurasian shorebirds but genetically distinct from N3 genes detected in other birds and geographical locations. The European gull viruses were further distinguishable from other influenza A viruses based on their PB2, NP, and NS genes. Gaining information on the full spectrum of avian influenza A viruses and creating reagents for their detection and identification will remain an important task for influenza surveillance, outbreak control, and animal and public health. We propose that sequence analyses of HA and NA genes of influenza A viruses be used for the rapid identification of existing and novel HA and NA subtypes.