Angioleiomyomas are infrequent benign tumors originating from smooth muscle cells of arterial or venous walls. They are most commonly seen in the lower extremities with a prevalence of only 8.5% in the head and neck. We present the case of a 40-year-old male patient who presented to Christian Medical College, Vellore, India, with recurrent episodes of right-sided epistaxis. A computed tomography scan showed an enlarged right inferior turbinate filling the right nasal cavity. The mass was removed endoscopically and sent to pathology. A diagnosis of angioleiomyoma of the nasal cavity was made. This location that has only been described in a minority of cases in the literature. Our case report signifies the importance of maintaining a broad differential when dealing with patients presenting with nasal mass and the importance of histopathological examination for the diagnosis.