The objectives of this study are (1) to evaluate hearing change after complete cholesteatoma resection in the setting of a labyrinthine fistula, (2) to assess the sensitivity and specificity of the preoperative CT-scan in diagnosing a labyrinthine fistula, and (3) to determine the correlation between the type of the labyrinthine fistula and its radiologic size. A retrospective chart review of all patients operated for cholesteatoma between 2004 and 2009 was conducted. Primary outcome was defined as the average variation in bone conduction thresholds (BCTs) as well as speech discrimination score (SDS) after total excision of cholesteatoma causing a labyrinthine fistula. We reviewed all preoperative CT-scans and operative notes to assess sensitivity and specificity for the diagnosis of a labyrinthine fistula. Results show that 317 patients underwent mastoidectomy for cholesteatoma. Twenty-eight patients were found to have 32 labyrinthine fistulas caused by cholesteatomatous disease affecting the lateral semi-circular canal (SCC) (n = 25), the superior SCC (n = 5), the posterior SCC (n = 1) and the footplate (n = 1). Postoperative BCT and SDS (24.5 dB; 86.6%) were neither clinically nor statistically different from preoperative levels (23.2 dB; 87.5%) (p = 0.35). Sensitivity and specificity of the preoperative high resolution 0.55 mm cuts CT-scan was 100%. With a fistula of 3.55 mm in the axial plan, a membraneous fistula must be suspected with a sensitivity of 66% and a specificity of 71%. Complete matrix resection without suctioning at the site of a cholesteatomatous labyrinthine fistula is a safe and effective management option. High-resolution preoperative CT-scan is very precise in diagnosing labyrinthine fistula and its radiologic size helps to predict the type of the fistula.