Hemangioblastomas are histologically benign tumors that occur exclusively within the neuraxis, most commonly in the posterior fossa. They are typically cystic tumors located in the cerebellum. Excision of the vascular mural nodules leads to cure. Brain stem lesions are rarely reported. Surgical extirpation of a solid brain stem hemangioblastoma is relatively risky and requires precise microsurgical techniques. We present a woman with a hemangioblastoma embedded in the medulla oblongata. This 33-year-old woman presented with occipital headaches and sensory ataxia. Complete and detailed preoperative imaging studies were followed by successful microsurgical excision of the lesion. The patient recovered completely within 2 weeks after the operation except for mild paresthesia of the legs. Preoperative magnetic resonance imaging and cerebral angiography provided important information regarding the nature, location, and blood supply of this lesion, which facilitated its total removal. The importance of intraoperative identification and control of the feeding artery of the tumor is emphasized.