Uterine smooth muscle tumors of uncertain malignant potential (STUMPs) are difficult both from the diagnostic and patient management standpoint because they cannot be classified as benign or malignant by conventional histologic criteria. This study's aim was to determine the diagnostic utility of allelic imbalance (AI) analysis in uterine smooth muscle tumors. Using microdissection and genotyping, we tested 5 leiomyomas, 6 STUMPs, and 10 leiomyosarcomas with follow-up for AI across a panel of seven tumor suppressor genes (p16, p21, p53, VHL, XRCC3, RB, and NM-23). None of the 6 patients with STUMP experienced recurrent disease, whereas 8 of the 10 patients diagnosed with leiomyosarcoma died of disease at follow-up. The mean frequency of allelic loss (FAL) for leiomyomas (18%) was not significantly different from that of STUMPs (21%) (P = 1), whereas leiomyosarcomas displayed a significantly higher FAL (52%) than both leiomyomas (P = 0.001) and STUMPs (P = 0.002). Loss of NM-23, a reported tumor metastasis suppressor gene, was found only in leiomyosarcomas (5 of 9, or 56%), and 4 of 5 (80%) of these were the only cases that demonstrated distant metastases (P = 0.04). Additionally, an FAL of >50% correlated with both NM-23 loss (P = 0.008) and distant metastatic disease (P = 0.04). In conclusion, leiomyomas and STUMPs displayed similar mean FALs and all were clinically benign, whereas uterine leiomyosarcomas had significantly higher frequencies of allelic loss than both leiomyomas and STUMPs. Molecular profiling may thus provide a valuable tool in assessment of malignancy in uterine smooth muscle tumors. Additionally, NM-23 is a promising candidate gene for determination of metastatic potential in these tumors.