Background: Cholecystocolonic fistula (CCF) is the second most common type of internal biliary fistula after cholecystoduodenal fistulas. Diagnosis is challenging due to its rarity and atypical biliary pain. Case report: 66-year-old female who presented with persistent nausea, and recurrent epigastric discomfort. Computer Tomography Scan (CT) and Magnetic Resonance Cholangio Pancreatography (MRCP) demonstrated choledocholithiasis but suspected a fistulising process to the gastrointestinal tract. She subsequently underwent endoscopic retrograde cholangiopancreatography (ERCP) for choledocholithiasis, which also confirmed the presence of CCF. The patient underwent successful cholecystectomy and surgical repair of CCF. Conclusion: The paucity of CCF in the reported literature is possibly hampered by the availability of modern imaging and procedural modalities, which enhances diagnostic accuracy and subsequent treatment strategies for this uncommon yet significant entity. This case illustrates the importance of considering CCF in differential diagnoses for patients with atypical biliary symptoms, particularly in the elderly with comorbidities. It is pivotal to involve a tertiary hepatobiliary unit for the optimal management of the condition.