Primary aortoenteric fistula (PAEF) is a potentially fatal condition which poses a considerable diagnostic challenge because of its infrequency and the nonspecific presentation. We report the case of a 61-year old woman who presented to her general practitioner with nonspecific and intermittent rectal bleeding, hematemesis, and weight loss. Four days later, she presented to the emergency department with worsening symptoms. The investigations revealed a new small 3.8-cm abdominal aortic aneurysm on computed axial tomography (CT), however, no evidence of a fistula was observed either on CT scan or endoscopy. Two days later, she became unstable requiring an emergency laparotomy and was taken to the operation theater for an en bloc resection of a segment of the aorta and duodenum with exclusion of the duodenum with an inline reconstruction of the aorta using a Dacron graft for a PAEF. The published data were reviewed to address the issues of optimal diagnostic methods and management of PAEF.