Melanoma is among the most lethal forms of cancer, accounting for 80% of deaths despite comprising just 5% of skin cancer cases. Treatment options remain limited due to the genetic and epigenetic mechanisms associated with melanoma heterogeneity that underlie the rapid development of secondary drug resistance. For this reason, the development of novel treatments remains paramount to the improvement of patient outcomes. Although the advent of chimeric antigen receptor-expressing T (CAR-T) cell immunotherapies has led to many clinical successes for hematological malignancies, these treatments are limited in their utility by their immune-induced side effects and a high risk of systemic toxicities. CAR natural killer (CAR-NK) cell immunotherapies are a particularly promising alternative to CAR-T cell immunotherapies, as they offer a more favorable safety profile and have the capacity for fine-tuned cytotoxic activity. In this review, the discussion of the prospects and potential of CAR-NK cell immunotherapies touches upon the clinical contexts of melanoma, the immunobiology of NK cells, the immunosuppressive barriers preventing endogenous immune cells from eliminating tumors, and the structure and design of chimeric antigen receptors, then finishes with a series of proposed design innovations that could improve the efficacy CAR-NK cell immunotherapies in future studies.