Recent theoretical studies have suggested that patterns of sequence divergence and relationships among alleles sampled from populations are affected by population size and rates of growth. However, the degree of concordance between changes to populations and to the patterns of allelic relationships within populations is not well understood. Threshold effects, time lags, or the effects of earlier demographic events may all prevent recent changes in population size from being reflected in the current patterns of allelic relationships. This has implications for analysis of species subject to recent fluctuations in population size. We have analyzed the patterns of sequence divergence and genealogy of mitochondrial DNA (mtDNA) alleles in the coconut crab, Birgus latro, using restriction enzyme analysis. Populations from the Pacific Ocean had mtDNAs with high diversity, a starlike phylogeny, and a Poisson distribution of sequence differences, i.e., the genetic signature of a rapidly expanding population. Yet population size in the Pacific has decreased dramatically (by at least an order of magnitude) over at least the last 100 to 1,000 years. In contrast to Pacific Ocean populations, the large protected population on Christmas Island (Indian Ocean) had a strongly structured mtDNA phylogeny with a multimodal distribution of sequence differences, as expected from a stable population. The obvious discrepancy between genetic and census data for the Pacific population is consistent with the view that the pattern of allelic relationships that we infer to have resulted from a past period of population growth is robust to further changes in population size. Thus, if a species is not in genetic equilibrium due to past growth events, then the effects of more recent events may not be detectable.