Tuberculosis (TB) is a leading killer from a single infectious agent globally. In 2019, Malaysia’s TB incidence rate was 92 per 100,000 population, and the TB mortality rate was estimated at 4 cases per 100,000 population per year. However, the state of Sabah had a higher burden of TB with a notification rate of 128 per 100,000 population and a TB case fatality rate of 8% compared to the national figure. This study aims to provide a comprehensive report on TB deaths epidemiology and its associated factors at a sub-national level. This nested case-control study used Sabah State Health Department TB surveillance data from the Malaysia national case-based TB registry (MyTB) between 2014 and 2018. Cases were defined as all-cause TB deaths that occurred before anti-TB treatment completion from the time of TB diagnosis. Controls were randomly selected from TB patients who completed anti-TB treatment. The TB mortality rate had increased significantly from 9.0/100,000 population in 2014 to 11.4/100,000 population in 2018. The majority of TB deaths occurred in the first two months of treatment. TB-related deaths were primarily due to advanced disease or disseminated TB, whereas non-TB-related deaths were primarily due to existing comorbidities. Many important independent risk factors for TB deaths were identified which are useful to address the increasing TB mortality rate.