Cholecystocolonic fistula (CF) is an uncommon type of internal biliary-enteric fistulas, which comprise rare complications of cholelithiasis and acute cholecystitis, with a prevalence of about 2% of all biliary tree diseases. We report a case of a spontaneous CF in a 75-year-old diabetic male admitted to hospital for the investigation of chronic watery diarrhea and weight loss. Massive pneumobilia demonstrated on abdominal ultrasound and computerized tomography, along with chronic, bile acid-induced diarrhea and a prolonged prothrombin time due to vitamin K malabsorption, led to the clinical suspicion of the fistula. Despite further investigation with barium enema and magnetic resonance cholangio-pancreatography, diagnosis of the fistulous tract between the gallbladder and the hepatic flexure of the colon could not be established preoperatively. Open cholecystectomy with fistula resection and exploration of the common bile duct was the preferred treatment of choice, resulting in an excellent postoperative clinical course. The incidence of biliary-enteric fistulas is expected to increase due to the parallel increase of iatrogenic interventions to the biliary tree with the use of endoscopic retrograde cholangio-pancreatography and the increased rate of cholecystectomies performed. Taking into account that advanced imaging techniques fail to demonstrate the fistulas tract in half of the cases, and that CFs usually present with non-specific symptoms, our report could assist physicians to keep a high index of clinical suspicion for an early and valid diagnosis of a CF.