Most colonially breeding animals occupy colonies that range in size from a few pairs to thousands of individuals, but the causes of colony size variation are largely unknown. Three general hypotheses are: (1) that variation in colony size is maintained by fluctuating selection via spatial and temporal changes in fitness associated with different colony sizes; (2) that colony formation reflects heterogeneity in habitat, with some sites having resources to support more individuals than others; and (3) that individuals assess the presence or annual reproductive success of current colony residents at each site and aggregate preferentially at high-quality sites. These hypotheses make predictions about how consistent colony size should be across sites and among years. We examined temporal and spatial variability of colony size for >200 Cliff Swallow (Petrochelidon pyrrhonota) colony sites in western Nebraska across a 30-year period. A colony's substrate type, annual population size in the study area, and whether the nesting season was relatively warm or cool, influenced average annual colony size. While some Cliff Swallow colony sites hosted perennially large colonies and others perennially small ones, between-year variability in colony size at most sites was high. Annual colony size distributions were relatively stable over 30 years and provided no evidence for long-term directional changes in colony size. The only ecological characteristic that was strongly associated with Cliff Swallow colony size at a site was the type of nesting substrate, with bridges tending to have larger colonies and being more frequently occupied than other substrates. Some sites showed annual changes in colony size consistent with the birds' basing their choice of colony on the presence or success of conspecifics, but many sites did not conform to a pattern expected if coloniality is a by-product of traditional aggregation. Colony size in Cliff Swallows was temporally and spatially unpredictable when viewed across the 30 years of this study. Each of the three hypotheses to explain size variation may have applied at certain sites, but the pattern of colony size variability leant the most support to the hypothesis that fluctuating selection on group size maintains colonies of widely different sizes.