Depressive disorders are highly prevalent in Africa where diseases such as HIV/AIDS are common. The aim of this study was to assess the validity of commonly used depression screening instruments in a setting characterized by low literacy, where patients may not be able to self-administer depression scales. We explored the validity of the Patient Health Questionaire-9 (PHQ-9), Centre for Epidemiological Surveys for Depression (CES-D), and the Kessler-10 (K-10), using the Mini International Neuropsychiatric Instrument (MINI) as a gold standard in 368 persons living with HIV/AIDS (PLWHA) in Uganda. The shorter versions of the K-10 and PHQ-9 were extracted to assess their performance in comparison to the longer versions. We used STATA 11.2 to analyze the data. The prevalence of a MINI defined depression in this patient sample was 17.4%. The three instruments all performed well, with areas under the curve (AUC) ranging from 0.82 to 0.96. The PHQ-9 showed the best performance characteristics with an AUC of 0.96, a sensitivity of 91.6%, and specificity 81.2%. The extracted versions performed more modestly. All three instruments showed good properties as screening tools; the PHQ-9 has particularly high sensitivity and specificity, and so can be considered useful for screening HIV-positive patients for depression.