Cell surface proteins, including transmembrane and other surface-anchored proteins, play a key role in several critical cellular processes and have a strong diagnostic value. The development of quick and robust experimental methods remains vital for the accurate and comprehensive characterization of the cell surface subproteome of individual cells. Here we present a high-throughput technique which relies on the biotinylation of the accessible primary amino groups in the extracellular segments of the proteins, using HL60 as a model cell line. Several steps of the method have been thoroughly optimized to capture labeled surface proteins selectively and in larger quantities. These include the following: improving the efficiency of the cell surface biotinylation; reducing the endogen protease activity; applying an optimal amount of affinity column and elution steps for labeled peptide enrichment; and examining the effect of various solid-phase extraction methods, different HPLC gradients, and various tandem mass spectrometry settings. Using the optimized workflow, we identified at least 1700 surface-associated individual labeled peptides (~6000–7000 redundant peptides) from the model cell surface in a single nanoHPLC-MS/MS run. The presented method can provide a comprehensive and specific list of the cell surface available protein segments that could be potential targets in various bioinformatics and molecular biology research.