Neurocognitive impairment (NCI) remains prevalent in the highly active antiretroviral therapy (HAART) era. Memory function is commonly affected. There is a need for a rapid, but sensitive screening tool. This study compares the Prospective and Retrospective Memory Questionnaire (PRMQ) and a computerised battery cognitive assessment to establish if the questionnaire has potential as a rapid screening tool for HIV-associated NCI. Neurologically asymptomatic patients with an undetectable HIV viral load on stable HAART were eligible to participate. Asymptomatic NCI (aNCI) was defined as a performance score more than 1SD below the normative mean in at least two domains of the computerised test. Memory impairment (MI) was defined as a t-score more than 1 SD below the normative mean using the PRMQ. Forty-five subjects participated. The mean age was 48 years (SD 11), the mean CD4 count was 546 cells/mul (SD 271), and 84% were male. Of subjects, 14/45 (24%) had NCI and 15/45 (33%) had MI. Two subjects had both types of impairment. No significant association was found between the presence of aNCI and MI (p = 0.229, r = 0.18, 95% CI -1.2, 0.23). aNCI was statistically significantly associated with younger age (p = 0.38, r = 0.31, 95% CI -0.02, 0.001). MI was statistically significantly associated with the set-shifting cognitive domain of the computerized battery (p = 0.04, r = 0.326) and time elapsed since HIV diagnosis (p = 0.035, r = 0.316). High rates of asymptomatic NCI were observed in this cohort, especially in younger individuals. The memory questionnaire did not reliably identify HIV-associated NCI other than executive function deficits and based on our data should therefore not be used as a rapid screening tool for this purpose.