Cutaneous melanoma (CM) is the most lethal form of skin cancer if it becomes metastatic, where treatment options and survival chances decrease dramatically. Immunotherapy treatments based on the immunologic checkpoint inhibitors programmed death cell protein 1 (PD-1) and cytotoxic T-lymphocyte antigen 4 (CTLA-4) constituted a main breakthrough in the treatment of metastatic CM, particularly for the achievement of long-term benefits. Even though it is a very promising therapy, resistance to primary immune checkpoint blockade (ICB) arises in about 70% of CM patients treated with a CTLA-4 inhibitor, and 40–65% of CM patients administered with a PD-1-targeting treatment. Some long non-coding RNAs (lncRNAs), and circular RNAs (circRNAs) are implicated in triggering pro- and anti-tumorigenic responses to various cancer treatments. The relationship between lncRNAs, circRNAs and ICB immunotherapy has not been explored in cutaneous metastatic melanoma (CMM). The aim of this pilot study is to evaluate the potential role of circRNA and lncRNA expression variability as pre-treatment predictor of the clinical response to immunotherapy in CMM patients. RNA-seq from 12 formalin-fixed paraffin-embedded (FFPE) samples from the metastatic biopsies of CMM patients treated with nivolumab was used to identify response-associated transcripts. Our findings indicate that specific lncRNAs and circRNAs, probably acting as competitive endogenous RNAs (ceRNAs), are involved in the regulatory networks of the immune response against metastatic melanoma that these patients have under treatment with nivolumab. Moreover, we established a risk score that yields predictions of the overall survival (OS) and progression-free survival (PFS) of CMM patients with high accuracy. This proof-of-principle work provides a possible insight into the function of ceRNAs, contributing to efforts to decipher the complex molecular mechanisms of ICB cancer treatment response.