Sinonasal mucosal melanoma is a rare tumor that develops slowly and may manifest with non specific signs and symptoms, causing significant delay in diagnosis. Local recurrence is common and usually occurs within the first two years after the initial treatment. Prognosis of recurrent lesions is poor and 5-year survival ranges between 10-47%. We report the clinical, radiographic, histopathological and immunohistochemical findings of a recurrent sinonasal mucosal melanoma which was diagnosed 10 years after the initial treatment, in a patient who presented with unilateral facial swelling and one-sided difficulty in breathing of two years duration. We discuss the causes of late diagnosis and review the negative predictive factors for recurrence and survival. As early diagnosis is of paramount importance for prognosis, we emphasize the signs and symptoms of patients with a history of sinonasal mucosal melanoma which should raise the suspicion for recurrence, in spite of a long time interval since diagnosis.