Single-cell analyses have revealed extensive intra- and inter-patient cancer heterogeneity, but this is not reflected in histologic stratification that is the foundation of many clinical decisions. Breast cancer classification is based on cellular organization and the expression of estrogen (ER) and progesterone (PR) hormone receptors, and whether HER2 (also known as ERBB2) is amplified. Therapies targeting hormone receptors and HER2 have improved outcomes for many patients, but intra-tumor cellular heterogeneity likely contributes to therapeutic resistance, relapse, and metastatic spread. To enhance histopathology analysis to the level of single-cell phenotypes, we used imaging mass cytometry (IMC) to analyze samples from 352 breast cancer patients for whom long-term survival data was available. We simultaneously measured 35 antibodies to create high-dimension immunohistochemistry pathology images. Single-cell segmentation and analysis quantified tumor and stromal single-cell phenotypes, their interactions, cellular communities and spatial heterogeneity. Classification based on multi-dimensional cellular composition and organization categorized the cellular structure of the breast cancer tumor microenvironment and identified novel breast cancer subtypes with distinct clinical prognosis within all clinical histopathology subgroups including hormone receptor positive and triple negative breast cancer.