The incidence of cutaneous malignant melanoma continues to rise in the United States. This deadly disease is potentially curable if caught at an early stage, however screening programs remain controversial. The United States Preventive Services Task Force cites insufficient evidence to recommend screening, by total-body skin examination (TBSE), for early detection of cutaneous melanoma. While definitive studies may be cost-prohibitive in the United States, more recent evidence suggests that organized programs to increase TBSE reduce mortality from melanoma. The positive impact of TBSE, and education regarding risk reduction and skin self-examination, is most likely to be cost-effective in high-risk patients such as middle-aged and older men. This population also includes those with changing moles or those who always or usually sunburn; those with melanoma in a first-degree relative, or dysplastic nevi or extensive moles; and those with high-risk ultraviolet (UV) exposure or other risk factors. The role of new technology, such as in-office and in-home dermoscopy, continues to evolve. Primary care clinicians are challenged in everyday practice to appropriately prioritize TBSE and empower their patients for “skin awareness” and self-detection of melanoma.