Verocay bodies are typically found in schwannoma and are often heralded as classical features of the lesion but they are not pathognomonic and can occasionally be found in other neoplasms, including leiomyomas and gastrointestinal stromal tumours (GIST) within the gastrointestinal (GI) tract. Hence, it is important to bear this differential diagnosis in mind and utilize an immunohistochemical panel to aid with the diagnosis. Here we present an unusual case of a 62-year-old male with an incidental rectal mass found on digital rectal examination upon presenting to urology with increased lower urinary tract symptoms. Histology of the rectal mass showed a spindle cell proliferation with prominent Verocay bodies seen throughout the specimen. Immunohistochemistry demonstrated that the tumour was positive for actin and desmin, negative for S100, DOG1, CD34 and CD117 (c-KIT), confirming it to being a Verocay body-prominent leiomyoma.