Melanoma is commonly diagnosed in a younger population than most other solid malignancies and, in Australia and most of the world, is the leading cause of skin-cancer-related death. Melanoma is a cancer type with high immunogenicity; thus, immunotherapies are used as first-line treatment for advanced melanoma patients. Although immunotherapies are working well, not all the patients are benefitting from them. A lack of a comprehensive understanding of immune regulation in the melanoma tumour microenvironment is a major challenge of patient stratification. Overexpression of CD155 has been reported as a key factor in melanoma immune regulation for the development of therapy resistance. A more thorough understanding of the actions of current immunotherapy strategies, their effects on immune cell subsets, and the roles that CD155 plays are essential for a rational design of novel targets of anti-cancer immunotherapies. In this review, we comprehensively discuss current anti-melanoma immunotherapy strategies and the immune response contribution of different cell lineages, including tumour endothelial cells, myeloid-derived suppressor cells, cytotoxic T cells, cancer-associated fibroblast, and nature killer cells. Finally, we explore the impact of CD155 and its receptors DNAM-1, TIGIT, and CD96 on immune cells, especially in the context of the melanoma tumour microenvironment and anti-cancer immunotherapies.