Mesenchymal tumors of the urinary bladder are a rare occurrence, the most common among them being leiomyoma of the bladder. These tumors commonly present with irritative urinary symptoms progressing gradually to obstructive symptoms as the size increases. We report on two patients who presented with lower urinary tract symptoms (LUTS). One of the patients also had concomitant bladder and uterine leiomyomata, which is the first such case to be reported in the literature. It is essential to differentiate leiomyoma from other common causes of LUTS. Cold cup biopsy has a significant false-negative rate and, in such cases, a wide local excision provides an optimal cure with excellent results.