A perivascular epithelioid cell tumor (PEComa) is an uncommon mesenchymal tumor composed of perivascular epithelioid cells. These tumor cells show variable immunoreactivity for both melanocytic and myogenic markers. Occurrence of PEComa has been reported at various anatomical sites, including the gynecological tract, uterus being the most common. Although most patients have sporadic PEComas, a subset may be associated with the inactivation of TSC1 or TSC2 genes and the occurrence of TFE3 gene fusions. However, a relationship between PEComas and other tumors is rare. We report a 41-year-old female patient with malignant PEComa who was admitted to the hospital with a complaint of vaginal bleeding. Because she had previously been diagnosed with colorectal and breast carcinomas at an early age, we performed a comprehensive genetic analysis to identify molecular alterations present in her background that unveiled multiple malignancy predispositions. Next-generation sequencing (NGS) analysis revealed two heterozygous germline pathogenic variants in the ATM and TP53 genes and a heterozygous variant of unknown significance (VUS) in the BRCA2 gene. The patient was diagnosed with the Li-Fraumeni Syndrome owing to the medical and family history and also the presentation of a pathogenic mutation of the TP53 gene. There are very few case reports in the literature describing PEComa in the Li-Fraumeni syndrome, and this is the first report of a uterine PEComa in a patient with Li-Fraumeni syndrome.