Chromatin boundary elements subdivide chromosomes in multicellular organisms into physically independent domains. In addition to this architectural function, these elements also play a critical role in gene regulation. Here we investigated the evolution of a Drosophila Bithorax complex boundary element called Fab-7, which is required for the proper parasegment specific expression of the homeotic Abd-B gene. Using a "gene" replacement strategy, we show that Fab-7 boundaries from two closely related species, D. erecta and D. yakuba, and a more distant species, D. pseudoobscura, are able to substitute for the melanogaster boundary. Consistent with this functional conservation, the two known Fab-7 boundary factors, Elba and LBC, have recognition sequences in the boundaries from all species. However, the strategies used for maintaining binding and function in the face of sequence divergence is different. The first is conventional, and depends upon conservation of the 8 bp Elba recognition sequence. The second is unconventional, and takes advantage of the unusually large and flexible sequence recognition properties of the LBC boundary factor, and the deployment of multiple LBC recognition elements in each boundary. In the former case, binding is lost when the recognition sequence is altered. In the latter case, sequence divergence is accompanied by changes in the number, relative affinity, and location of the LBC recognition elements.