The bithorax complex (BX-C) in Drosophila melanogaster is a cluster of homeotic genes that determine body segment identity. Expression of these genes is governed by cis-regulatory domains, one for each parasegment. Stable repression of these domains depends on Polycomb Group (PcG) functions, which include trimethylation of lysine 27 of histone H3 (H3K27me3). To search for parasegment-specific signatures that reflect PcG function, chromatin from single parasegments was isolated and profiled. The H3K27me3 profiles across the BX-C in successive parasegments showed a ‘stairstep’ pattern that revealed sharp boundaries of the BX-C regulatory domains. Acetylated H3K27 was broadly enriched across active domains, in a pattern complementary to H3K27me3. The CCCTC-binding protein (CTCF) bound the borders between H3K27 modification domains; it was retained even in parasegments where adjacent domains lack H3K27me3. These findings provide a molecular definition of the homeotic domains, and implicate precisely positioned H3K27 modifications as a central determinant of segment identity.