This study investigated peptide accumulation and bitterness in reduced- and full-fat Cheddar cheeses that were manufactured with single-strain Lactococcus lactis starters that had distinct cell envelope proteinase specificities. Micellar electrokinetic capillary electrophoresis of aqueous cheese extracts detected three large peaks, designated O, P, and Q, that eluted with peptide standards and increased in area during cheese maturation in a pattern that was distinct for each starter. Regression analysis of bitter flavor scores from trained sensory panels and individual OQ peak areas suggested that peaks P and Q had a negative and positive correlation, respectively, to this defect. Then, HPLC, capillary electrophoresis, peptide sequencing, and mass spectrometry were used to identify five peptides from αS1-casein (CN), one from β-CN, and one from αS2-CN that accumulated in 6-mo-old cheeses. Most of the peptides derived from αS1-CN (f 1–23) accumulated in a manner that corresponded with starter proteinase specificity. All of the peptides identified in the study except αS2-CN (f 1–21) eluted in the O-P-Q region of micellar electrokinetic capillary electropherograms. The αS1-CN (f 1–16), αS1-CN (f 1–17) and β-CN (f 193-209) eluted in peak O, αS1-CN (f 1–13) and αS1-CN (f 1–14) eluted in peak P, and αS1-CN (f 1–9) eluted in peak Q.