Perivascular epithelioid cell tumor (PEComas) are a group of ubiquitous neoplasms described in different organs that share distinctive morphologic, immunohistochemical, ultrastructural, and genetic features. They have been reported in several organs such as the uterus, lung, kidney, liver, small and large bowel, and prostate. To the best of our knowledge, only 8 cervical PEComa cases have been described. We report the case of a 43-yr-old woman who presented with abnormal uterine bleeding. Clinical diagnosis of a malignant cervical lesion followed an excision, histopathologically evaluated as PEComa. The hysterectomy specimen confirmed the diagnosis by strong HMB-45 positivity, weak S100 positivity, and focal, moderate cytoplasmic TTF-1 positivity, and negative melan A, SMA, desmin, vimentin, cytokeratins, CD1a and other markers. The patient was negative for tuberous sclerosis complex, did not receive additional therapy, and 3 yr later is disease free. Cervical PEComas are very rare tumors but have to be considered in the differential diagnosis of cervical lesions exhibiting unusual cytologic and immunohistochemical characteristics.