After the Russian Federation, Ukraine is the country of the Former Soviet Union experiencing the greatest epidemics of tuberculosis (TB) and HIV, although complete official data are not available. This study investigates the prevalence of HIV among new TB patients in the civilian and penitentiary populations of Donetsk Oblast. A cross-sectional survey was undertaken of 1507 new patients with TB (1351 civilians, 156 prisoners) between January and June 2006. The prevalence of HIV among patients with TB was 15.5% (95% confidence interval 13.7-17.6) and 23.7% (95% CI 17.3-31.2) in the civilian and penitentiary sectors, respectively. Reported injecting drug use was the strongest independent predictor for HIV infection, followed by young age (25-44 y). Being prisoners was also found a significant independent predictor for HIV infection (OR: 1.5, 95% CI 1.1-2.1). In conclusion, the prevalence of HIV in the TB population is the highest ever reported in Ukraine, almost 2 times higher than the World Health Organization estimates for 2005 (7.9%), and 3 percentage points higher than the official data reported. These findings call for urgent measures to control HIV and, consequently, HIV-related TB.