Determining the prognostic association of different immune cell types in the tumor microenvironment is critical for understanding cancer biology and developing new therapeutic strategies. However, this is challenging in certain cancer types, where the abundance of different immune subsets is highly correlated. In this study, we develop a computational method named TimiGP to overcome this challenge. Based on bulk gene expression and survival data, TimiGP infers cell-cell interactions that reveal the association between immune cell relative abundance and prognosis. As demonstrated in metastatic melanoma, TimiGP prioritizes immune cells critical in prognosis based on the identified cell-cell interactions. Highly consistent results are obtained by TimiGP when applied to seven independent melanoma datasets and when different cell-type marker sets are used as inputs. Additionally, TimiGP can leverage single-cell RNA sequencing data to delineate the tumor immune microenvironment at high resolutions across a wide range of cancer types.