Cell labeling and tracking methodologies can play an important role in experiments aimed at understanding biological systems. However, many current cell labeling and tracking techniques have limitations that preclude their use in a variety of multiplexed and high-throughput applications that could best represent the heterogeneity and combinatorial complexity present in physiologic contexts. Here, we demonstrate an approach for labeling, tracking, and quantifying cells using double-stranded DNA barcodes. These barcodes are introduced to the outside of the cell membrane, giving the labeled cells a unique identifier. This approach is compatible with flow cytometric and PCR-based identification and relative quantification of the presence of barcode-labeled cells. Further, utilizing this strategy, we demonstrate the capacity for sorting and enrichment of barcoded cells from a bulk population. In addition, we illustrate the design and utility of a range of orthogonal barcode sequences, which can enable the use of multiple independent barcodes to track, sort, and enrich multiple cell types and/or cells receiving distinct treatments from a pooled sample. Overall, this method of labeling cells has the potential to track multiple populations of cells in both high-throughput in vitro and physiologic in vivo settings.