Vascular malformations associated with neoplasms are extremely rare. Herein we report an extraordinary coincidence of arteriovenous malformation (AVM) and gastrointestinal stromal tumor (GIST) in the jejunum. A 44-year-old woman presented with melena and anemia. Abdominal computed tomography revealed a highly vascularized, strong early arterial enhancing soft tissue mass in the jejunum, which was confirmed by angiography to be an AVM supplied by the distal jejunal branch of the superior mesenteric artery. An emergency operation was performed due to active gastrointestinal (GI) bleeding. The resected jejunum showed a protruding, mostly solid subserosal mass. The mass was confirmed to be a spindle cell type GIST and was intermingled with the AVM located in the overlying submucosa and muscularis propria. To our knowledge, this is the first reported case of an AVM associated with a GIST. This case masqueraded radiologically as an AVM alone and presented clinically with GI bleeding.