Uterine leiomyomas (LMs), currently the most common gynecological complaint around the world, are a serious medical, social and economic problem. Accurate diagnosis is the necessary prerequisite of the diagnostic-therapeutic process. Statistically, mistakes may occur more often in case of disease entities with high prevalence rates. Histopathology, based on increasingly advanced immunohistochemistry methods, is routinely used in the diagnosis of neoplastic diseases. Markers of the highest sensitivity and specificity profiles are used in the process. As far as LMs are concerned, the crux of the matter is to identify patients with seemingly benign lesions which turn out to be suspicious (e.g., atypical LM) or malignant (e.g., leiomyosarcoma (LMS)), which is not uncommon. In this study, we present the current state of knowledge about the use of immunohistochemical markers in the differential diagnosis of LM, atypical LM, smooth muscle tumors of uncertain malignant potential (STUMP), and LMS, as well as their clinical predictive value.