BACKGROUND: Tracheostomy is a life-saving procedure whose outcomes may vary between hospitals based on disparities in their existing expertise. We aimed at establishing the indications, early tracheostomy-related complications and their associated factors in Uganda. METHODS: In a prospective cohort study, we consecutively enrolled one-hundred patients, both adults and children 2 h post-tracheostomy procedure. At baseline, information on patients' socio-demographics, tracheostomy indications, pre- and post-procedural characteristics was collected through researcher administered questionnaires and from medical records. Clinical examination was performed at baseline but also at either day 7 or whenever a tracheostomy-related complication was suspected during the 7 days follow-up. Comparison of patients' baseline characteristics, tracheostomy indications and complications across two hospitals was done using Pearson's chi-square. For predictors of early tracheostomy complications, bivariate and multivariate analysis models were fitted using binomial regression in STATA 13.0 software. RESULTS: All patients underwent surgical tracheostomy. Majority were adults (84%) and males (70%). The commonest tracheostomy indications were; pulmonary toilet (58%) and anticipated prolonged intubation (42%). Overall, 53% (95% CI: 43.0 - 62.7) had early complications with the commonest being tube obstruction (52.6%). Independent predictors of early tracheostomy-related complications were; anticipated prolonged intubation as an indication (RR = 1.8, 95%CI: 1.19 - 2.76), Bjork flap tracheal incision (RR = 1.6, 95%CI: 1.09 - 2.43), vertical tracheal incision (RR = 1.53, 95%CI: 1.02 - 2.27), and age below 18 years (RR = 1.22, 95%CI: 1.00 - 1.47). CONCLUSION: Pulmonary toilet is the commonest tracheostomy indication at major hospitals in Uganda. The incidence of early tracheostomy complications is high and majorly related to post-procedure tracheostomy tube management. Having anticipated prolonged intubation as an indication for tracheostomy, a Bjork flap or vertical tracheal incisions and being a child were associated with increased risk of complications. Emphasis on multidisciplinary team care, standardization of tracheostomy care protocols, and continuous collection of patient data as well as paying attention to patient quality of life factors such as early return to oral feeding, ambulation and normal speech may have great potential for improved quality of tracheostomy care in low resource settings.