We present a case of pigmented olfactory neuroblastoma of the nostril and nasal cavity that was positive for neural cell adhesion molecule (CD56) and initially diagnosed as melanoma based on patchy S-100 protein positivity. This is a possible pitfall in the microscopic diagnosis of an entity that can be confused with melanoma histologically. Usually, CD56 is thought of as a marker for natural killer cell lymphoma, but our case highlights the usefulness of CD56 in dermatopathology because mucosal biopsy specimens are occasionally sent to dermatopathology laboratories for evaluation. It also illustrates the need for an immunostaining panel on unusual pigmented tumors.