The occurrence of leiomyoma of the rectum is uncommon. Most of these lesions are clinically silent and are found incidentally during laparotomy or endoscopic procedures for unrelated conditions. Symptomatic leiomyomas of the rectum are encountered less frequently, with only sporadic reports in the literature. We describe a case of a leiomyoma of the rectum presenting as recurrent lower gastrointestinal hemorrhage and secondary anemia.