CENP-A is a centromere-specific variant of histone H3 that is required for accurate chromosome segregation. The fission yeast Schizosaccharomyces pombe and mammalian Mis16 and Mis18 form a complex essential for CENP-A recruitment to centromeres. It is unclear, however, how the Mis16-Mis18 complex achieves this function. Here, we identified, by mass spectrometry, novel fission yeast centromere proteins Mis19 and Mis20 that directly interact with Mis16 and Mis18. Like Mis18, Mis19 and Mis20 are localized at the centromeres during interphase, but not in mitosis. Inactivation of Mis19 in a newly isolated temperature-sensitive mutant resulted in CENP-A delocalization and massive chromosome missegregation, whereas Mis20 was dispensable for proper chromosome segregation. Mis19 might be a bridge component for Mis16 and Mis18. We isolated extragenic suppressor mutants for temperature-sensitive mis18 and mis19 mutants and used whole-genome sequencing to determine the mutated sites. We identified two groups of loss-of-function suppressor mutations in non-sense-mediated mRNA decay factors (upf2 and ebs1), and in SWI/SNF chromatin-remodeling components (snf5, snf22 and sol1). Our results suggest that the Mis16-Mis18-Mis19-Mis20 CENP-A-recruiting complex, which is functional in the G1-S phase, may be counteracted by the SWI/SNF chromatin-remodeling complex and non-sense-mediated mRNA decay, which may prevent CENP-A deposition at the centromere.