Gulls are important hosts of avian influenza A viruses (AIVs) and gull AIVs often contain gene segments of mixed geographic and host lineage origins. In this study, the prevalence of AIV in gulls of Newfoundland, Canada from 2008 to 2011 was analyzed. Overall prevalence was low (30/1645, 1.8%) but there was a distinct peak of infection in the fall. AIV seroprevalence was high in Newfoundland gulls, with 50% of sampled gulls showing evidence of previous infection. Sequences of 16 gull AIVs were determined and analyzed to shed light on the transmission, reassortment and persistence dynamics of gull AIVs in Atlantic North America. Intercontinental and waterfowl lineage reassortment was prevalent. Of particular note were a wholly Eurasian AIV and another with an intercontinental reassortant waterfowl lineage virus. These patterns of geographic and inter-host group transmission highlight the importance of characterization of gull AIVs as part of attempts to understand global AIV dynamics.