A rare cause of gastrointestinal bleeding is an aortoenteric fistula, which typically occurs after previous aortic surgeries and is referred to as a secondary aortoenteric fistula (SAEF). A 74-year-old male smoker with a medical history of open surgical repair of an infrarenal aortic aneurysm in 2009 was admitted to the emergency department with shortness of breath on mild exertion, weakness, and melena for the past two weeks. During hospitalization, he experienced a sudden episode of abdominal pain, abundant hematochezia, and shock. An abdominal computed tomography (CT) angiography revealed a distal aortic anastomotic pseudoaneurysm with contrast extravasation, confirming the presence of an aortoenteric fistula. The patient underwent endovascular abdominal aortic aneurysm repair (EVAR) via bilateral femoral access, and empirical antibiotic therapy was initiated. Aortoenteric fistulas should be considered in patients with a history of aortic aneurysm repair who present with recurrent melena or hematochezia, despite normal upper and lower endoscopic examinations. A herald bleed, occurring prior to a massive hemorrhage, is crucial for early diagnosis, as there may be limited time for further investigations.