Background: New diagnoses of tuberculosis (TB) present important opportunities to detect and treat HIV. Rates of HIV and TB in Indonesia's easternmost Papua Province exceed national figures, but data on co-infection rates and outcomes are lacking. We aimed to measure TB-HIV co-infection rates, examine longitudinal trends, compare management with World Health Organisation (WHO) recommendations, and document progress and outcome.Methods: Adults with newly-diagnosed smear-positive pulmonary TB managed at the Timika TB clinic, Papua Province, were offered voluntary counselling and testing for HIV in accordance with Indonesian National Guidelines, using a point-of-care antibody test. Positive tests were confirmed with 2 further rapid tests. Study participants were assessed using clinical, bacteriological, functional and radiological measures and followed up for 6 months.Results: Of 162 participants, HIV status was determined in 138 (85.2%), of whom 18 (13.0%) were HIV+. Indigenous Papuans were significantly more likely to be HIV+ than Non-Papuans (Odds Ratio [OR] 4.42, 95% confidence interval [CI] 1.38-14.23). HIV prevalence among people with TB was significantly higher than during a 2003-4 survey at the same TB clinic, and substantially higher than the Indonesian national estimate of 3%. Compared with HIV- study participants, those with TB-HIV co-infection had significantly lower exercise tolerance (median difference in 6-minute walk test: 25 m, p = 0.04), haemoglobin (mean difference: 1.3 g/dL, p = 0.002), and likelihood of cavitary disease (OR 0.35, 95% CI 0.12-1.01), and increased occurrence of pleural effusion (OR 3.60, 95% CI 1.70-7.58), higher rates of hospitalisation or death (OR 11.80, 95% CI 1.82-76.43), but no difference in the likelihood of successful 6-month treatment outcome. Adherence to WHO guidelines was limited by the absence of integration of TB and HIV services, specifically, with no on-site ART prescriber available. Only six people had CD4+ T-cell counts recorded, 11 were prescribed co-trimoxazole and 4 received ART before, during or after TB treatment, despite ART being indicated in 14 according to 2006 WHO guidelines.Conclusions: TB-HIV co-infection in southern Papua, Indonesia, is a serious emerging problem especially among the Indigenous population, and has risen rapidly in the last 5 years. Major efforts are required to incorporate new WHO recommendations on TB-HIV management into national guidelines, and support their implementation in community settings.