The identification and quantification of proteins lags behind DNA-sequencing methods in scale, sensitivity, and dynamic range. Here, we show that sparse amino acid-sequence information can be obtained for individual protein molecules for thousands to millions of molecules in parallel. We demonstrate selective fluorescence labeling of cysteine and lysine residues in peptide samples, immobilization of labeled peptides on a glass surface, and imaging by total internal reflection microscopy to monitor decreases in each molecule's fluorescence after consecutive rounds of Edman degradation. The obtained sparse fluorescent sequence of each molecule was then assigned to its parent protein in a reference database. We tested the method on synthetic and naturally derived peptide molecules in zeptomole-scale quantities. We also fluorescently labeled phosphoserines and achieved single-molecule positional readout of the phosphorylated sites. We measured >93% efficiencies for dye labeling, survival, and cleavage; further improvements should enable studies of increasingly complex proteomic mixtures, with the high sensitivity and digital quantification offered by single-molecule sequencing.