Triple-negative breast cancer (TNBC) is an aggressive and complex subtype of breast cancer that lacks targeted therapy. TNBC manifests characteristic, extensive intratumoral heterogeneity that promotes disease progression and influences drug response. Single-cell techniques in combination with next-generation computation provide an unprecedented opportunity to identify molecular events with therapeutic potential. Here, we describe the generation of a comprehensive mass cytometry panel for multiparametric detection of 23 phenotypic markers and 13 signaling molecules. This single-cell proteomic approach allowed us to explore the landscape of TNBC heterogeneity, with particular emphasis on the tumor microenvironment. We prospectively profiled freshly resected tumors from 26 TNBC patients. These tumors contained phenotypically distinct subpopulations of cancer and stromal cells that were associated with the patient's clinical status at the time of surgery. We further classified the epithelial-mesenchymal plasticity of tumor cells, and molecularly defined phenotypically diverse populations of tumor-associated stroma. Furthermore, in a retrospective tissue-microarray TNBC cohort, we showed that the level of CD97 at the time of surgery has prognostic potential.