Pseudomyogenic hemangioendothelioma (PHE) is a rare indolent vascular tumor that typically has a multifocal presentation and involves multiple tissue planes. This report describes a 34-year-old man with multiple infiltrated brown papules and plaques on his left leg that had evolved for 6 months. The skin biopsy revealed a dermal and subcutaneous neoplasm composed of fascicles of spindle cells with atypia and epithelioid cells with prominent nucleoli and abundant eosinophilic cytoplasm. There was no evidence of necrosis, and the mitotic rate was low. There was strong reactivity with cytokeratin AE1/AE3, ERG, and FLI1, multifocal reactivity with smooth muscle actin, and focal reactivity with CD31. There was no expression of keratin MNF116, CAM5.2, CD34, CAMTA1, S100-protein, epithelial membrane antigen, melan-A, HMB-45, factor XIIIa, HHV8, or CD10. The nuclei of neoplastic cells showed intact expression of INI1. The clinical, histological, and immunophenotypical aspects were consistent with a diagnosis of PHE. A lower limb CT scan showed lesions in the skin, muscle, and bone planes. The patient was sent to an oncology center, where he maintains regular clinical and imagiological follow-up.