H2AZ is a widely conserved histone variant that is implicated in protecting euchromatin from the spread of heterochromatin. H2AZ is incorporated into nucleosomes as a heterodimer with H2B, by the SWR1 ATP-dependent chromatin-remodeling complex. We have identified a homolog of H2AZ in the protozoan parasite Trypanosoma brucei, along with a novel variant of histone H2B (H2BV) that shares approximately 38% sequence identity with major H2B. Both H2AZ and H2BV are essential for viability. H2AZ localizes within the nucleus in a pattern that is distinct from canonical H2A and is largely absent from sites of transcription visualized by incorporation of 5-bromo-UTP (BrUTP). H2AZ and H2BV colocalize throughout the cell cycle and exhibit nearly identical genomic distribution patterns, as assessed by chromatin immunoprecipitation. H2AZ co-immunoprecipitates with H2BV but not with histones H2B or H2A nor with the variant H3V. These data strongly suggest that H2AZ and H2BV function together within a single nucleosome, marking the first time an H2AZ has been shown to associate with a non-canonical histone H2B.