We describe a case of primary intramural, extraluminal leiomyosarcoma of the common iliac artery. The patient presented with pelvic and leg pain and pheochromocytoma-like symptoms. The diagnosis was made intraoperatively, the tumor was resected, vascular reconstruction was performed, and postoperative radiation therapy was administered. Primary leiomyosarcoma of a major peripheral artery is extremely rare, and this report examines the clinical presentation, treatment, and prognosis of these patients.