Centromeric histone H3, CENP-ACse4, is essential for faithful chromosome segregation. Stringent regulation of cellular levels of CENP-ACse4 restricts its localization to centromeres. Mislocalization of CENP-ACse4 is associated with aneuploidy in yeast and flies and tumorigenesis in human cells; thus defining pathways that regulate CENP-A levels is critical for understanding how mislocalization of CENP-A contributes to aneuploidy in human cancers. Previous work in budding yeast shows that ubiquitination of overexpressed Cse4 by Psh1, an E3 ligase, partially contributes to proteolysis of Cse4. Here we provide the first evidence that Cse4 is sumoylated by E3 ligases Siz1 and Siz2 in vivo and in vitro. Ubiquitination of Cse4 by the small ubiquitin-related modifier (SUMO)-targeted ubiquitin ligase (STUbL) Slx5 plays a critical role in proteolysis of Cse4 and prevents mislocalization of Cse4 to euchromatin under normal physiological conditions. Accumulation of sumoylated Cse4 species and increased stability of Cse4 in slx5∆ strains suggest that sumoylation precedes ubiquitin-mediated proteolysis of Cse4. Slx5-mediated Cse4 proteolysis is independent of Psh1, since slx5∆ psh1∆ strains exhibit higher levels of Cse4 stability and mislocalization than either slx5∆ or psh1∆ strains. Our results demonstrate a role for Slx5 in ubiquitin-mediated proteolysis of Cse4 to prevent its mislocalization and maintain genome stability.