Eukaryotic DNA mismatch repair requires the concerted action of several proteins, including proliferating cell nuclear antigen (PCNA) and heterodimers of MSH2 complexed with either MSH3 or MSH6. Here we report that MSH3 and MSH6, but not MSH2, contain N-terminal sequence motifs characteristic of proteins that bind to PCNA. MSH3 and MSH6 peptides containing these motifs bound PCNA, as did the intact Msh2-Msh6 complex. This binding was strongly reduced when alanine was substituted for conserved residues in the motif. Yeast strains containing alanine substitutions in the PCNA binding motif of Msh6 or Msh3 had elevated mutation rates, indicating that these interactions are important for genome stability. When human MSH3 or MSH6 peptides containing the PCNA binding motif were added to a human cell extract, mismatch repair activity was inhibited at a step preceding DNA resynthesis. Thus, MSH3 and MSH6 interactions with PCNA may facilitate early steps in DNA mismatch repair and may also be important for other roles of these eukaryotic MutS homologs.