Although diagnosis of high-grade uterine mesenchymal tumors (UMTs) exhibiting classic morphologic features is straightforward, diagnosis is more challenging in tumors in which prototypical features are poorly developed, focal, and/or coexist with features seen in other neoplasms. Here, we sought to define the repertoire of somatic genetic alterations in diagnostically challenging UMTs with myomelanocytic differentiation, including some reported as perivascular epithelioid cell tumors (PEComas). In 17 samples from 15 women, the tumors were histologically heterogenous. Immunohistochemical expression of at least 1 melanocytic marker (HMB45, Melan-A, or MiTF) was identified in all tumors, and of myogenic markers (desmin or smooth muscle actin) in most tumors. Targeted massively parallel sequencing revealed several genetic alterations, most commonly in TP53 (41% mutation, 12% deletion), TSC2 (29% mutation, 6% deletion), RB1 (18% deletion), ATRX (24% mutation), MED12 (12% mutation), BRCA2 (12% deletion), CDKN2A (6% deletion) as well as FGFR3, NTRK1, and ERBB3 amplification (each 6%). Gene rearrangements (JAZF1-SUZ12; DNAJB6-PLAG1; and SFPQ-TFE3) were identified in 3 tumors. Integrating histopathologic, immunohistochemical, and genetic findings, tumors from 4 patients were consistent with malignant PEComa (1 TFE3-rearranged); 6 were classified as leiomyosarcomas; 3 showed overlapping features of PEComa and other sarcoma types (leiomyosarcoma or low-grade endometrial stromal sarcoma); and 2 were classified as sarcoma, not otherwise specified. Our findings suggest that diagnostically challenging UMTs with myomelanocytic differentiation represent a heterogenous group of neoplasms which harbor a diverse repertoire of somatic genetic alterations; these genetic alterations can aid classification.