The budding yeast histone H3 variant, Cse4, replaces conventional histone H3 in centromeric chromatin and, together with centromere-specific DNA-binding factors, directs assembly of the kinetochore, a multiprotein complex mediating chromosome segregation. We have identified Scm3, a nonhistone protein that colocalizes with Cse4 and is required for its centromeric association. Bacterially expressed Scm3 binds directly to and reconstitutes a stoichiometric complex with Cse4 and histone H4 but not with conventional histone H3 and H4. A conserved acidic domain of Scm3 is responsible for directing the Cse4-specific interaction. Strikingly, binding of Scm3 can replace histones H2A-H2B from preassembled Cse4-containing histone octamers. This incompatibility between Scm3 and histones H2A-H2B is correlated with diminished in vivo occupancy of histone H2B, H2A, and H2AZ at centromeres. Our findings indicate that nonhistone Scm3 serves to assemble and maintain Cse4-H4 at centromeres and may replace histone H2A-H2B dimers in a centromere-specific nucleosome core.