Abstract Background Interaction between malignant cells and immune cells that reside within the tumor microenvironment (TME) modulate different aspects of tumor development and progression. Recent works showed the importance of miRNA-containing extracellular vesicles in this crosstalk. Methods Interested in understanding the interplay between melanoma and immune-related TME cells, we characterized the TCGA’s metastatic melanoma samples according to their tumor microenvironment profiles, HLA-I neoepitopes, transcriptome profile and classified them into three groups. Moreover, we combined our results with melanoma single-cell gene expression and public miRNA data to better characterize the regulatory network of circulating miRNAs and their targets related to immune evasion and microenvironment response. Results The group associated with a worse prognosis showed phenotypic characteristics that favor immune evasion, including a strong signature of suppressor cells and less stable neoantigen:HLA-I complexes. Conversely, the group with better prognosis was marked by enrichment in lymphocyte and MHC signatures. By analyzing publicly available melanoma single-cell RNA and microvesicle microRNAs sequencing data we identified circulating microRNAs potentially involved in the crosstalk between tumor and TME cells. Candidate miRNA/target gene pairs with previously reported roles in tumor progression and immune escape mechanisms were further investigated and demonstrated to impact patient’s overall survival not only in melanoma but across different tumor types. Conclusion Our results underscore the impact of tumor-microenvironment interactions on disease outcomes and reveal potential non-invasive biomarkers of prognosis and treatment response.