Avian influenza virus (AIV) in wild birds has been of increasing interest over the last decade due to the emergence of AIVs that cause significant disease and mortality in both poultry and humans. While research clearly demonstrates that AIVs can move across the Pacific or Atlantic Ocean, there has been no data to support the mechanism of how this occurs. In spring and autumn of 2010 and autumn of 2011 we obtained cloacal swab samples from 1078 waterfowl, gulls, and shorebirds of various species in southwest and west Iceland and tested them for AIV. From these, we isolated and fully sequenced the genomes of 29 AIVs from wild caught gulls (Charadriiformes) and waterfowl (Anseriformes) in Iceland. We detected viruses that were entirely (8 of 8 genomic segments) of American lineage, viruses that were entirely of Eurasian lineage, and viruses with mixed American-Eurasian lineage. Prior to this work only 2 AIVs had been reported from wild birds in Iceland and only the sequence from one segment was available in GenBank. This is the first report of finding AIVs of entirely American lineage and Eurasian lineage, as well as reassortant viruses, together in the same geographic location. Our study demonstrates the importance of the North Atlantic as a corridor for the movement of AIVs between Europe and North America.