Background: Population-wide screening for melanoma is unlikely to be cost-effective. Nevertheless, targeted surveillance of high-risk individuals may be. Objectives: To estimate the cost effectiveness of various surveillance strategies in the UK population, stratified by risk using a simple self-assessment tool scoring between 0 and 67. Methods: A decision model comparing alternative surveillance policies from the perspective of the UK National Health Service over 30 years was developed. The strategy with the highest expected net benefit for each risk score was identified, resulting in a compound risk-stratified policy describing the most cost-effective population-wide strategy. The overall expected cost and quality-adjusted life-years (QALYs), the incremental cost-effectiveness ratio, and associated uncertainty were reported. Results: The most cost-effective strategy is for those with a Williams score of 15 to 21 (relative risk [RR] of 0.79–1.60 vs. a mean score of 17 in the United Kingdom) to be offered a one-off full-body skin examination, and for those with a score of 22 or more (RR 1.79+) to be enrolled into a quinquennial monitoring program, rising to annual recall for those with a risk score greater than 43 (RR 20.95+). Expected incremental cost would be £164 million per annum (~0.1% of the National Health Service budget), gaining 15,947 additional QALYs and yielding an incremental cost-effectiveness ratio of £10,199/QALY gained (51.3% probability <£30,000). Conclusions: The risk-stratified policy would be expensive to implement but cost-effective compared with typical UK thresholds (£20,000–£30,000/QALY gained), although decision uncertainty is high. Phased implementation enrolling only higher risk individuals would be substantially less expensive, but with consequent foregone health gain.