BACKGROUND: In sub-Saharan Africa, as high as 2/3 of tuberculosis patients are HIV/AIDS co-infected and tuberculosis is the most common cause of death among HIV/AIDS patients worldwide. Tuberculosis and HIV co-infections are associated with special diagnostic and therapeutic challenges and constitute an immense burden on healthcare systems of heavily infected countries like Ethiopia. The aim of the study was to determine the prevalence of pulmonary tuberculosis and their immunologic profiles among HIV positive patients. METHODS: A cross sectional study was conducted among adult HIV-positive patients attending HIV/AIDS clinic of Gondar University Hospital. Clinical and laboratory investigations including chest x-ray and acid fast staining were used to identify tuberculosis cases. Blood samples were collected to determine CD4+ lymphocyte count. A structured questionnaire was used to collect socio-demographic characteristics of study subjects. The data was entered and analyzed using SPSS version 16 software. RESULTS: A total of 400 HIV positive study participants were enrolled. Thirty (7.5%, 95%CI: 5.2-10.6%) of the study participants were found to have pulmonary tuberculosis. In multivariate analysis, only CD4+ lymphocyte count (AOR = 2.9; 95% CI: 1.002-8.368) was found to be independently associated with tuberculosis-HIV co-infection. Individuals who had advanced WHO clinical stage were also statistically significant for co-infection. The mean CD4+ lymphocyte count of HIV mono-infected participants were 296 +/- 192 Cells/mm3 and tuberculosis-HIV co-infected patients had mean CD4+ lymphocyte count of 199 +/- 149 Cells/mm3 with p value of 0.007. CONCLUSIONS: We found high prevalence of tuberculosis-HIV co-infection. Lower CD4+ lymphocyte count was found to be the only predicting factor for co-infection. Early detection of co-infection is very necessary to prolong their ART initiation time and by then strengthening their immune status.