A 50-year-old Japanese woman consulted our hospital complaining of hematochezia. Colonoscopic examination showed Borrmann type 1 rectal carcinoma in the lower rectum, which was later demonstrated to be mucinous adenocarcinoma of Dukes' class A. Along with carcinoma, there was a small sessile polyp with a central depression that mimicked a submucosal tumor. Histologically, the polyp demonstrated tubular structures that coursed from the top of the polypoid surface to the deep submucosa. The tubular structure was 6 mm in length and showed abortive dichotomous branching. It was mainly lined by ciliated pseudostratified columnar to more cuboidal epithelium. Along with the tubular structure, there were bundles of smooth muscle cells and lobules of seromucinous glands. There was no cartilage. The pathological diagnosis was heterotopic respiratory mucosa (HRM) arising in the rectum. To our knowledge, this is the first reported case of HRM in the rectum.