Background: Data on non-specific effects of BCG vaccination in well described, general population African cohorts is scanty. We report the effects of BCG vaccination on post-neonatal infant and post-infancy mortality in a cohort of children in Mbale, Eastern Uganda. Methods: A community-based prospective cohort study was conducted between January 2006 and February 2014. A total of 819 eligible pregnant women were followed up for pregnancy outcomes and survival of their children up to 5 years of age. Data on the children's BCG vaccination status was collected from child health cards at multiple visits between 3 weeks and 7 years of age. Data was also collected on mothers' residence, age, parity, household income, self-reported HIV status as well as place of birth. Multivariable Cox proportional hazards regression models taking into account potential confounders were used to estimate the association between BCG vaccination and child survival. Results: The neonatal mortality risk was 22 (95% CI: 13, 35), post-neonatal infant mortality 21 (12, 34) per 1,000 live births and the mortality risk among children between 1 and 5 years of age (post-infancy) was 63 (47, 82) per 1,000 live births. The median age at BCG vaccination was 4 days. Out of 819 children, 647 (79%) had received the BCG vaccine by 24 weeks of age. In the adjusted analysis, the rate of post-neonatal death among infants vaccinated with BCG tended to be nearly half of that among those who had not received the vaccine (adjusted HR: 0.47; 95% CI: 0.14, 1.53). BCG vaccination was associated with a lower rate of death among children between 1 and 5 years of age (adjusted HR: 0.26; 95% CI: 0.14, 0.48). Conclusion: The risk of early childhood death in Mbale, Uganda is unacceptably high. BCG vaccination was associated with an increased likelihood of child survival.