We have studied the viability of targeted molecular screening for the identification of female patients with hereditary leiomyomatosis and renal cell cancer (HLRCC) syndrome. Affected patients harbor a germ-line heterozygous mutation of the fumarate hydratase (FH) gene. Clinically, some patients present with aggressive renal cell carcinoma. Concerning women, in almost all cases, this is preceded by symptomatic uterine leiomyoma. We aimed to identify women operated on for symptomatic leiomyoma by the age of 30. Archived paraffin-embedded leiomyoma tissue was tested for the FH gene mutation in 14 cases. Two patients with multiple leiomyomas and with the confirmed germ-line mutations c.1433_1434dupAAA, p.(Lys477dup) and c.953A>T, p.(His318Leu) were identified and enrolled in a surveillance program. Statistically significant correlation between the presence of multiple uterine leiomyomas (more than seven in our experience) and the FH gene mutation was found. The immunohistochemical expression pattern, of simultaneous FH absence and S-(2-succino)cysteine (2SC) positivity, correlated with the results of the molecular genetic study in only one case. The histomorphologically simultaneous detection of enlarged nucleoli with a clear halo of leiomyocyte nuclei, their fibrillary cytoplasm, the presence of eosinophilic globules, and staghorn vessels proved to be only a partially sensitive indicator of HLRCC-associated leiomyoma and fully correlated with immunohistochemistry and molecular genetic study only in one case. Molecular genetic testing is presently the only reliable diagnostic tool able to identify HLRCC patients. The sensitivity and specificity of the presence of multiple leiomyomas in women with the FH gene mutation who are younger than 30 years old should be confirmed in larger scale studies. The applied targeted molecular screening protocol proved to be effective, resulting in identification of two positive patients out of fourteen tested individuals.