The interaction of tumor cells with their environment and particularly the immune system is increasingly recognized as a key factor of tumorigenesis and tumor progression. However, the expression levels of genes alone cannot capture directly the complexity of these interactions, and a more elaborated framework is necessary. We propose a new cell-cell interactions (CCIs) feature space based on scRNA-Seq data of multiple patient samples to classify cancers into subtypes at the patient level. Specifically, we transform gene expression profiles into a redefined feature space that takes into account interactions between ligands and receptors across all possible pairs of cell types for each patient. To handle the ultrahigh dimensionality arising from the hundreds of thousands of CCIs, we propose an ensemble feature selection algorithm to prioritize the most discriminatory CCIs. Our machine learning pipeline identifies a set of CCIs that accurately classifies cancer samples into subtypes. We apply our computational framework, named pCCI, to the Pancreatic Ductal Adenocarcinoma and Glioblastoma Multiforme subtypes classification, achieving high classification performance. Our work provides compelling evidence that the CCI space can successfully reveal differences in the microenvironment of different cancer subtypes and identify novel pharmacological targets.