Objectives: To explore changes over time in the epidemiology of tuberculosis (TB) in Denmark in people living with human immunodeficiency virus (HIV) (PLWH). Methods: In this nationwide, population-based cohort study we included all adult PLWH from the Danish HIV Cohort Study (1995–2017) without previous TB. We estimated TB incidence rate (IR), all-cause mortality rate (MR), associated risk and prognostic factors using Poisson regression. Results: Among 6982 PLWH (73 596 person-years (PY)), we observed 217 TB events (IR 2.9/1000 PY, 95% CI 2.6–3.4: IR 6.7, 95% CI 5.7–7.9 among migrants and IR 1.4, 95% CI 1.1–1.7 among Danish-born individuals; p < 0.001). The IR of concomitant HIV/TB remained high and unchanged over time. The IR of TB diagnosed >3 months after HIV diagnosis declined with calendar time, longer time from HIV diagnosis, and CD4 cell recovery. Independent TB risk factors were African/Asian/Greenland origin (adjusted incidence rate ratio (aIRR) 5.2, 95% CI 3.5–7.6, aIRR 6.5, 95% CI 4.2–10.0, aIRR 7.0, 95% CI 3.4–14.6, respectively), illicit drug use (aIRR 6.9, 95% CI 4.2–11.2), CD4 <200 cells/μL (aIRR 2.7, 95% CI 2.0–3.6) and not receiving antiretroviral therapy (aIRR 3.7, 95% CI 2.5–5.3). Fifty-five patients died (MR 27.9/1000 PY, 95% CI 21.4–36.3), with no improvement in mortality over time. Mortality prognostic factors were Danish-origin (adjusted mortality rate ratio (aMRR) 2.3, 95% CI 1.3–4.3), social burden (aMRR 3.9, 95% CI 2.2–7.0), CD4 <100 cells/μL at TB diagnosis (aMRR 2.6, 95% CI 1.3–4.9), TB diagnosed >3 months after HIV versus concomitant diagnosis (aMRR 4.3, 95% CI 2.2–8.7) and disseminated TB (aMRR 3.3, 95% CI 1.1–9.9). Conclusion: Late HIV presentation with concomitant TB remains a challenge. Declining TB rates in PLWH were observed over time and with CD4 recovery, highlighting the importance of early and successful antiretroviral therapy. However, MR remained high. Our findings highlight the importance of HIV and TB screening strategies and treatment of latent TB in high-risk groups.