Background: HIV-associated neurocognitive disorders (HAND) remain prevalent despite improved antiretroviral treatment (ART), and it is essential to have a sensitive and specific HAND screening tool. Methods: Participants were 200 HIV-infected US military beneficiaries, managed early in the course of HIV infection, had few comorbidities, and had open access to ART. Participants completed a comprehensive, seven-domain (16-test), neuropsychological battery (~120 min); neurocognitive impairment (NCI) was determined using a standardized score derived from demographically adjusted T-scores (global deficit score ≥0.5). Restricting the estimated administration time of the screening battery to < = 20 minutes, we examined the sensitivity and specificity of detecting NCI for all possible combinations of 2-, 3-, and 4- tests from the comprehensive battery. Results: Participants were relatively healthy (median CD4 count: 546 cells/mm3) with 64% receiving ART. Prevalence of NCI was low (19%). The best 2-test screener included the Stroop Color Test and the Hopkins Verbal Learning Test-Revised (11 min; sensitivity = 73%; specificity = 83%); the best 3-test screener included the above measures plus the Paced Auditory Serial Addition Test (PASAT; 16 min; sensitivity = 86%; specificity = 75%). The addition of Action Fluency to the above three tests improved specificity (18 min; sensitivity = 86%; specificity = 87%). Conclusions: Combinations of widely accepted neuropsychological tests with brief implementation time demonstrated good sensitivity and specificity compared to a time intensive neuropsychological test battery. Tests of verbal learning, attention/working memory, and processing speed are particularly useful in detecting NCI. Utilizing validated, easy to administer, traditional neuropsychological tests with established normative data may represent an excellent approach to screening for NCI in HIV.