We present two rare cases of rectal leiomyoma originating in muscularis mucosae. The lesions were incidentally discovered in a 58-years-old woman and 53-years-old man during colonoscopy performed for unrelated symptoms. Both presented as small polyps and were removed by conventional colonoscopic snare polypectomy without clinical recurrence. Gross examination revealed pedunculated polyps covered by non-ulcerated mucosa. Histologically the lesions represent smooth muscle cells proliferation originating in muscularis mucosae. Both lesions were uniformly positive for SMA and DESM and negative for CD34, CD117 and S100. These tumors have a different clinical course than gastrointestinal stromal tumors; since morphologic appearance is sometimes confusing, CD117 staining is mandatory for an accurate diagnostic. We decided to present these cases because of the rarity of this condition concerning both the location and the origins of tumors. We stress the importance of the proper classification of this rare lesion, considering its outmost importance.