We developed a Markov process model for colony-site dynamics of Gull-billed Terns (Sterna nilotica). From 1993 through 1996, we monitored breeding numbers of Gull-billed Terns and their frequent colony associates, Common Terns (Sterna hirundo) and Black Skimmers (Rynchops niger), at colony sites along 80 km of the barrier island region of coastal Virginia. We also monitored flooding events and renesting. We developed the model for colony survival, extinction, and recolonization at potential colony sites over the four-year period. We then used data on annual site occupation by Gull-billed Terns to estimate model parameters and tested for differences between nesting substrates (barrier island vs. shellpile). Results revealed a dynamic system but provided no evidence that the dynamics were Markovian, i.e. the probability that a site was occupied in one year was not influenced by whether it had been occupied in the previous year. Nor did colony-level reproductive success the previous season seem to affect the probability of site occupancy. Site survival and recolonization rates were similar, and the estimated overall annual probability of a site being occupied was 0.59. Of the 25 sites that were used during the four-year period, 16 were used in one or two years only, and only three were used in all four years. Flooding and renesting were frequent in both habitat types in all years. The frequent flooding of nests on shellpiles argues for more effective management; augmentation with shell and sand to increase elevations as little as 20 cm could have reduced flooding at a number of sites. The low colonysite fidelity that we observed suggests that an effective management approach would be to provide a large number of sand and/or shellpile sites for use by nesting terns. Sites not used in one year may still be used in subsequent years.