Despite the existence of 10 avian paramyxovirus (APMV) serotypes, very little is known about the distribution, host species, and ecological factors affecting virus transmission. To better understand the relationship among these factors, we conducted APMV wild bird surveillance in regions of Ukraine suspected of being intercontinental (north to south and east to west) flyways. Surveillance for APMV was conducted in 6,735 wild birds representing 86 species and 8 different orders during 2006 to 2011 through different seasons. Twenty viruses were isolated and subsequently identified as APMV-1 (n = 9), APMV-4 (n = 4), APMV-6 (n = 3), and APMV-7 (n = 4). The highest isolation rate occurred during the autumn migration (0.61%), with viruses isolated from mallards, teals, dunlins, and a wigeon. The rate of isolation was lower during winter (December to March) (0.32%), with viruses isolated from ruddy shelducks, mallards, white-fronted geese, and a starling. During spring migration, nesting, and postnesting (April to August) no APMV strains were isolated out of 1,984 samples tested. Sequencing and phylogenetic analysis of four APMV-1 and two APMV-4 viruses showed that one APMV-1 virus belonging to class 1 was epidemiologically linked to viruses from China, three class II APMV-1 viruses were epidemiologically connected with viruses from Nigeria and Luxembourg, and one APMV-4 virus was related to goose viruses from Egypt. In summary, we have identified the wild bird species most likely to be infected with APMV, and our data support possible intercontinental transmission of APMVs by wild birds.