Abstract Objective To determine frequency of palatal fistula following primary cleft palate repair and the associated factors as a measure of cleft palate repair outcome and its challenges at a cleft centre in Uganda. Results Between May and December 2016, 54 children with cleft palate were followed up at Comprehensive Rehabilitation services of Uganda (CoRSU) hospital, from time of primary cleft palate repair until at least 3 months postoperative to determine whether they developed palatal fistula or not. Frequency of palatal fistula was 35%. Factors associated with increased fistula formation were cleft width wider than 12 mm (p = 0.006), palatal index greater than 0.4 (p = 0.046), presence of malnutrition at initial outpatient assessment (p = 0.0057) and at time of surgery (p = 0.008), two-stage palate repair (p = 0.005) and postoperative infection (p = 0.003). Severe clefting (palatal index greater than 0.4) was seen in 74% of patients and malnutrition (Low weight for age) seen in 48% of patients. Palatal fistula rates at our institution were high compared to reports in literature. The high proportions of severe clefting and malnutrition observed in our population that was also poor and unable to afford feeding supplements increased likelihood of fistula formation and posed challenges to achieving low fistula rates in our setting.