Abstract Background Over the last decade tuberculosis (TB) incidence and mortality in Brazil have been steadily declining. However, this downward trend has not been observed among HIV-infected patients. We describe the epidemiological and clinical profile of TB patients by HIV status using the Brazilian National Surveillance System. Methods All TB diagnoses with HIV status information between January 1, 2007 and December 31, 2011 were categorized as either HIV or non-HIV at time of TB diagnosis. Co-infected patients (TB-HIV) were compared to TB patients with no HIV-infection using a hierarchical logistic regression model using Stata 13.0. Results The prevalence of TB-HIV co-infection was 19% among adults ≥ 15 years of age. We analyzed data from 243,676 individuals, of whom 46,466 were TB-HIV and 197,210 were only TB cases. The following factors increased risk of co-infection: male sex (OR: 1.06, 95% CI 1.03-1.10), 20 to 39 years of age (OR = 4.82, 95% CI 4.34-5.36), black (OR = 1.08, 95% CI 1.04-1.13), 4–7 years of education (OR = 1.13, 95% CI 1.19-1.28), diagnosed following default (OR = 2.65, 95% CI 1.13-6.25), presenting with pulmonary and extra-pulmonary forms of TB simultaneously (OR = 2.80, 95% CI 1.56-5.02), presenting with histopathologic examination suggestive of TB (OR = 2.15, 95% CI 1.13-4.07). Co-infected patients were less likely to live in rural areas (OR = 0.45, 95% CI 0.42-0.48), have diabetes (OR = 0.45, 95% CI 0.40-0.50) and be smear positive (OR = 0.55, 95% CI 0.32-0.95), and co-infected patients had higher risk of default (OR = 2.96, 95% CI 2.36-3.71) and death from TB (OR = 5.16, 95% CI 43.04-5.77). Conclusions The prevalence of co-infection with HIV among TB patients is 19% in Brazil. By identifying predictors of co-infection targeted interventions can be developed to prevent both TB and HIV, and to diagnose each disease earlier and ultimately decrease poor treatment outcomes and death.