Triple-negative breast cancer (TNBC), the poorest-prognosis breast cancer subtype, lacks clinically approved biomarkers for patient risk stratification, treatment management, and immunotherapies. Prior literature has shown that interrogation of the tumor-immune microenvironment (TIME) may be a promising approach for the discovery of novel biomarkers that can fill these gaps. Recent developments in high-dimensional tissue imaging technology, such as multiplexed ion beam imaging (MIBI), provide spatial context to protein expression in the TIME, opening doors for in-depth characterization of cellular processes. We developed a computational pipeline for the robust examination of the TIME using MIBI. We discover that profiling the functional proteins involved in cell-to-cell interactions in the TIME predicts recurrence and overall survival in TNBC. The interactions between CD45RO and Beta Catenin and CD45RO and HLA-DR were the most relevant for patient stratification. We demonstrated the clinical relevance of the immunoregulatory proteins PD-1, PD-L1, IDO, and Lag3 by tying their interactions to recurrence and survival. Multivariate analysis revealed that our methods provide additional prognostic information compared to clinical variables. Our novel computational pipeline produces interpretable results, and is generalizable to other cancer types.