Objective: Since its publication, there have been limited studies evaluating the utility of the Neuropsychological Assessment Battery (NAB) Mazes subtest in a clinical setting. Here, we evaluated the construct validity of the NAB Mazes subtest, as compared to other traditional neuropsychological measures, in an urban HIV-infected cohort. The relationship between NAB Mazes and CD4+ T-cell nadir was also explored. Method: A total of 62 HIV-infected, predominantly African-American participants (36 males, 26 females), aged 23–71 years old (M = 42.9, SD = 11.3) were recruited through the Comprehensive NeuroAIDS Center at Temple University School of Medicine. A series of Pearson product-moment correlations were conducted to examine convergent and divergent validity between NAB Mazes and the following domains: Attention/Working Memory, Processing Speed, Executive Functioning, Verbal Fluency, Verbal Learning, Verbal Memory, Fine Motor, and Mood Disturbance. Each domain consists of the average of one or more conceptually related neuropsychological test scores. NAB Mazes was also compared to reported CD4+ T-cell nadirs. Results: NAB Mazes was significantly correlated (p < .05) with Attention/Working Memory (r = .327), Processing Speed (r = .547), Executive Functioning (r = .430), and Fine Motor (r = .327). A non-significant relationship (p = .906) was found between NAB Mazes and CD4+ T-cell nadir. Conclusion: In this preliminary study of HIV-infected participants, we demonstrate that NAB Mazes has convergent validity with measures of attention/working memory, processing speed, executive functioning, and fine motor skills. Divergent validity was demonstrated between NAB Mazes and tests of verbal abilities and level of mood disturbance. NAB Mazes was not associated with a biomarker of severity of HIV disease.