Infection with the human immunodeficiency virus (HIV) is a pandemic that has taken a staggering toll on sub-Saharan Africa. The virus is neurotropic and it is the most prevalent viral infection of the nervous system in history. This study aimed at determining the frequency and pattern of neurological complications in HIV-infected patients and correlating these with the degree of immunosuppression as determined by the CD4+ count levels. Methods A case-controlled study. Fifty-two consecutive seropositive patients and 50 healthy seronegative controls satisfying the inclusion criteria participated in the study. The two groups were age-and sex-matched. Detailed history was obtained from, and a comprehensive physical examination with focus on the neurological system done on, each participant. Laboratory investigations were done as indicated. Cognitive function was assessed using the Community Screening Interview for Dementias while HIV encephalopathy was diagnosed using the International Classification of Disease (ICD) Volume 10 criteria. Patients and controls also had autonomic function testing done. Statistical package for social sciences (SPSS) was used in the statistical analysis. In all cases, a p-value of < 0.05 was taken as being significant. Results Neurological complications were found in 81% of the patients with the commonest findings being autonomic dysfunction in 69.4% and distal symmetrical polyneuropathy (DSP) in 53.9%. Craniopathies and HIV encephalopathy were not uncommon with a third and tenth respectively of the patients having these. These results (i.e. of autonomic dysfunction, DSP, craniopathies and HIV encephalopathy) when compared with those for the seronegative controls were statistically significant with p<0.05 in each case. However, no statistically significant association was found between likelihood of complications and the CD4+ count levels. Conclusions Neurological complications of HIV are common in this environment, their spectrum is wide, and no part of the neuraxis is spared. HIV infection should be considered in the differential diagnoses of patients with cranial and peripheral neuropathies in this environment