Discussion regarding the diagnosis, prognosis, and management of giant congenital nevocellular nevi (GCNN) has permeated the literature because of concerns regarding malignant potential. As a derivative of dysgenetic neural crest development, GCNN histology in the neonate may be quite variable and not easily discernible from malignant melanoma, presenting a diagnostic dilemma to both the seasoned pathologist and surgeon. Here we present an interesting case of GCNN arising from a large encephalocele in a neonate. In spite of a clinically aggressive course, histology repeatedly failed to meet the criteria for melanoma until the diagnosis of malignant melanoma was made at autopsy. Clinical suspicion for malignancy must be high when evaluating atypical large nevi, and prompt surgical management is necessary to protect against the risk for malignant melanoma.