Cellular neurothekeoma (CNT) is a benign dermal tumor mainly affecting the head and neck and the upper extremities. It is characterized histologically by interconnecting fascicles of plump spindle or epithelioid cells with ample cytoplasm infiltrating in the reticular dermis. The histogenesis of CNT has been controversial, although it is generally regarded as an immature counterpart of classic/myxoid neurothekeoma, a tumor with nerve sheath differentiation. Two rare cases of CNT containing melanin-laden cells were described. Immunohistochemical study with NKI/C3, vimentin, epithelial membrane antigen, smooth muscle antigen, CD34, factor XIIIa, collagen type IV, S100 protein and HMB-45 was performed. Both cases showed typical growth pattern of CNT with interconnecting fascicles of epithelioid cells infiltrating in collagenous stroma. One of the nodules contained areas exhibiting atypical cytological features. Melanin-laden epithelioid or dendritic cells were diffusely scattered throughout one nodule, and focally present in the peripheral portion of the other nodule. Both nodules were strongly immunoreactive to NKI/C3 and vimentin, but negative to all the other markers employed. CNT harboring melanin-laden cells may pose diagnostic problems because of their close resemblance to nevomelanocytic lesions and other dermal mesenchymal tumors. These peculiar cases may also provide further clues to the histogenesis of CNT.