Peptic ulcer disease (PUD) is a very common condition, with an annual incidence ranging from 0.1% to 0.3% and a lifetime prevalence ranging from 5% to 10%. If not treated, it can lead to severe complications such as gastro-intestinal bleeding, perforation, or entero-biliary fistula. Entero-biliary fistulas and especially choledocho-duodenal fistula (CDF) are a rare, but relevant and important diagnosis, which can lead to several complications such as gastric outlet obstruction, bleeding, perforation, or recurrent cholangitis. In this article, we present the case of an 85-year-old woman with PUD complicated with gastro-intestinal bleeding and a CDF. We also performed a review of the literature to search for pre-existing cases with this atypical clinical presentation. The aim was to raise awareness among surgeons and clinicians by offering a summary of different types of entero-biliary and especially CDF, existing diagnostic investigations, and management.