Composite hemangioendothelioma (CHE) is a rare, locally aggressive, vascular tumor of intermediate-/ low-grade malignancy, and is characterized by varying combinations of benign, low-grade malignant, and malignant vascular components. In cutaneous localization, only 22 cases have been reported so far. A new case of CHE of the gluteal region in a 58-year-old man is described. Microscopically, vascular neoplasm, situated mainly within the deep dermis and the subcutaneous fat tissue, was composed of sinusoidal hemangioma, arteriovenous hemangioma, retiform hemangioendothelioma (RHE), and angiosarcoma. An average number of mitoses within the angiosarcomatous component was 10 per 10 high-power fields. Immunohistochemically, the tumor cells were positive for factor VIII-related antigen, CD34, and CD31 and negative for D2-40 and GLUT-1. Ki-67 labeling index was 21%, 1.2%, and 0% in the areas of angiosarcoma, RHE, and sinusoidal hemangioma, respectively. No recurrent disease was noted 3 months after the surgery. The present case displayed the following features previously undescribed in CHE: a novel component of sinusoidal hemangioma and localization at the gluteal region. We also provide review of clinical, histopathological, and immunohistochemical characteristics of cutaneous CHE from the published cases.