The identification of increasingly powerful prognostic factors has led to sequential modifications of the cutaneous melanoma staging system. Changes in the staging system are anticipated as more refined prognostic factors are identified. This article provides an overview of the system, including a brief history and an introduction to recent advances in staging of patients with primary melanoma (i.e., sentinel lymphadenectomy). Practical recommendations for a stage-specific workup for the patient, which are especially important given the need for quality care in an increasingly cost-conscious environment, are provided.