People with HIV may report neurocognitive complaints, with or without associated neurocognitive impairment, varying between individuals and populations. While the HIV genome could play a major role, large systematic viral genome-wide screens to date are lacking. The Swiss HIV Cohort Study biannually enquires neurocognitive complaints. We quantified broad-sense heritability estimates using partial 'pol' sequences from the Swiss HIV Cohort Study resistance database and performed a viral near full-length genome-wide association study for the longitudinal area under the curve of neurocognitive complaints. We performed all analysis (i) restricted to HIV Subtype B and (ii) including all HIV subtypes. From 8547 people with HIV with neurocognitive complaints, we obtained 6966 partial 'pol' sequences and 2334 near full-length HIV sequences. Broad-sense heritability estimates for presence of memory loss complaints ranged between 1% and 17% (Subtype B restricted 1-22%) and increased with the stringency of the phylogenetic distance thresholds. The genome-wide association study revealed one amino acid (Env L641E), after adjusting for multiple testing, positively associated with memory loss complaints (P = 4.3 * 10^-6 ). Other identified mutations, while insignificant after adjusting for multiple testing, were reported in other smaller studies (Tat T64N, Env *291S). We present the first HIV genome-wide association study analysis of neurocognitive complaints and report a first estimate for the heritability of neurocognitive complaints through HIV. Moreover, we could identify one mutation significantly associated with the presence of memory loss complaints. Our findings indicate that neurocognitive complaints are polygenetic and highlight advantages of a whole genome approach for pathogenicity determination.