Prior studies have reported higher HIV prevalence among prisoners than the general population in Brazil, but data have been derived from single prisons. The aim of this study was to evaluate HIV testing practices, prevalence and linkage to care among inmates in a network of 12 prisons. Methods We administered a questionnaire to a population-based sample of inmates from 12 prisons in Central-West Brazil and collected sera for HIV and syphilis testing from January to December 2013. We evaluated factors associated with HIV testing and infection using multivariable logistic regression models. Six months after HIV testing, we assessed whether each HIV-infected prisoner was engaged in clinical care and whether they had started antiretroviral therapy. Results We recruited 3,362 inmates, of whom 2,843 (85%) were men from 8 prisons, and 519 (15%) were women from 4 prisons. Forty-five percent of participants reported never having been tested for HIV previously. In multivariable analysis, the variables associated with previous HIV testing were lack of a stable partner (adjusted odds ratio [AOR]: 1.38; 95% CI: 1.18– 1.60), completed more than four years of schooling (AOR 1.40; 95% CI: 1.20–1.64), history of previous incarceration (AOR: 1.68; 95% CI: 1.43–1.98), history of mental illness (AOR 1.52; 95% CI: 1.31–1.78) and previous surgery (AOR 1.31; 95% CI: 1.12–1.52). Fifty-four (1.6%) of all participants tested positive for HIV; this included 44 (1.54%) men and 10 (1.92%) women. Among male inmates, HIV infection was associated with homosexuality (AOR 6.20, 95% CI: 1.73–22.22), self-report of mental illness (AOR 2.18, 95% CI: 1.13– 4.18), history of sexually transmitted infections (AOR 3.28, 95% CI: 1.64–6.56), and syphilis sero-positivity (AOR 2.54, 95% CI: 1.20–5.39). Among HIV-infected individuals, 34 (63%) were unaware of their HIV status; only 23 of these 34 (68%) newly diagnosed participants could be reached at six month follow-up, and 21 of 23 (91%) were engaged in HIV care. Conclusions HIV testing rates among prison inmates are low, and the majority of HIV-infected inmates were unaware of their HIV diagnosis. Incarceration can be an opportunity for diagnosis and treatment of HIV among vulnerable populations who have poor access to health services, but further work is needed on transitional HIV care for released inmates.