There is still controversy over the criteria for malignancy of smooth muscle tumors (SMTs) of the uterus. We examined 51 cellular SMTs using immunohistochemistry for MIB-1, proliferating cell nuclear antigen (PCNA), p53, HHF35, alpha-smooth muscle actin (SMA), and flow cytometry. Morphologically, the 51 cases were classified into 24 leiomyosarcomas (LMS), two uncertain malignant potential, four bizarre leiomyomas, and 21 cellular leiomyomas. The mean values of the MIB-1 and PCNA indices showed significant differences between LMS and benign SMTs. p53 cells were positive in eight of 24 leiomyosarcomas, and 12 of 22 were aneuploid. HHF35 and alpha-SMA showed a diffuse positivity in almost all the benign SMTs. In contrast, 10 of the 24 LMS were either focally positive or negative for SMA. Using a logistic regression model, at cut-off points of 3.6 on the MIB-1 index and 15.6 on the PCNA index, the LMS and the benign SMTs were classified with an overall accuracy of 92% and 82%, respectively. Moreover, by combining the MIB-1 index and alpha-SMA positivity, the cut-off point could be established at 0.492 on the probability scale with the highest overall accuracy of 96%. Regarding the prognosis of LMS, p53 positivity was correlated with survival (p = 0.0357). A combination of the MIB-1 index and alpha-SMA was helpful in distinguishing between LMS and benign SMT. Moreover, p53 positivity was considered to be a good marker for predicting the prognosis of LMS.