Seventy-six lactococci isolates from 2 protected designation of origin (PDO) cheeses were studied for their acidification ability, proteolytic activity, and inhibitory activities as well as their intraspecies characterization by randomly amplified polymorphic DNA-polymerase chain reaction (RAPD-PCR). Fifty-two of them were characterized as Lactococcus lactis subsp. lactis by the SDS-PAGE of whole-cell proteins. The test strains increased the amount of acid in milk from 6 to 24 h as well as the quantities of amino acids on incubation for 4 d. The majority of the isolates degraded preferentially αs-casein. The isolates from Feta differed from those of Graviera Kritis in respect of β-casein degradation. This fragment was either not degraded or underwent a small degradation by lactococci from Feta. A stronger intensity of acidification for the isolates from Feta and a higher casein breakdown ability for those from Graviera Kritis were also recorded. Lactococci from Feta and Graviera Kritis inhibited, preferentially, the growth of Escherichia coli O157:H7, and Yersinia enterocolitica, respectively. A high heterogeneity among the isolates according to RAPD-PCR was determined, as well as grouping of the isolates according to their source of isolation. Selected isolates from each cheese could be used as starters to make either Feta or Graviera Kritis.