We examined changing patterns of distribution of two large mammalian predators, the raccoon (Procyon lotor) and red fox (Vulpes vulpes), and beach-nesting terns and Black Skimmers (Rynchops niger) along ca. 80 km of the Virginia barrier island landscape between the periods 1975-1977 and 1998. Based on evidence from trapping, scent stations, den observations and sightings of the two predators, there has been a marked increase in their island ranges. In 1975-77, only 6 of the 11 surveyed barrier islands definitely harbored at least one of the two mammals, but by 1998, 11 of 14 islands showed evidence of one or both during the spring and summer. Concurrently, annual beach-nesting bird surveys have been conducted since the mid 1970s during June. From 1977 to 1998, the number of colonies of terns [Common (Sterna hirundo), Gull-billed (S. nilotica), Least (S. antillarum), Royal (S. maxima), and Sandwich (S. sandvicensis)] and Black Skimmers declined from 23 colonies on 11 barrier islands to 13 colonies on 10 islands. In addition, the populations decreased dramatically for all species except the marginal Sandwich Tern and Least Tern. This pattern suggests that mammalian predation may be a major factor in colony site selection or success, although we have no data on success at most locations. The only consistently large colony over the years has been the Royal Tern colony on Fisherman Island, one of the few with no resident large mammals. Because these declining waterbirds appear to be running out of options for safe colony sites in coastal Virginia, we discuss the prospects of conducting limited predator removals on certain islands. In addition, considerations of strict management and enforcement of protection at critical manmade colony sites that now attract large numbers of certain species, are timely. Lastly, where dredged material disposal projects are planned, providing nesting sites for these colonial species and roosting sites for migrant birds may be appropriate.