In this report, we describe 13 cases of primary neurofibrosarcoma of the skin. The tumor presumably arises from small cutaneous nerves, is locally aggressive, and has a potential for metastasis. Characteristic histopathologic features include proliferating atypical spindle cells with slender wavy and pointed nuclei; hypocellular areas with loose, myxoid stroma; and areas of organoid organization such as palisading, whorly, storiform, and tactile body-like formations. The S-100 stain is positive in about 60% of cases. In the current series, most tumors arose in deep dermis and were grade 2 malignant lesions with a moderate degree of cytologic atypia and 2 or fewer mitoses in 10 high-power fields. Three patients died of their malignant lesion. Only two tumors metastasized. Of the 10 patients who had local recurrence, 5 had multiple recurrent lesions. Neurofibrosarcoma should be considered in the differential diagnosis of malignant tumors of the skin. A complete surgical resection of the primary tumor with adequate margins of surrounding normal-appearing tissue is advised.