The association between malaria and HIV co-infection has begun to emerge with each disease adversely affecting the other. These diseases are endemic in the developing nations, particularly sub-saharan Africa. The infection rates of both diseases can be reduced by behavioural changes, barrier protection (condoms or bed nets) and medical prophylaxis. The association between malaria parasitaemia and CD4 cell counts in HIV sero-positive patients was investigated in order to determine the pattern in our environment and to provide useful suggestions for early diagnosis and treatment or prophylaxis of patients. A randomized cross-sectional and prospective study consisting of 480 study subjects aged 17 to 65 years (mean ±SD: 32.99 ± 9.80) was carried out from May – November 2006 (rainy season). Among them, 160 were HIV sero-positive and malaria positive, 160 malaria positive only who were neither on antiretroviral nor anti-malarial drugs and 160 healthy controls. Most of the subjects (69%) were in their third and fourth decades. Among those with dual infection, 20%, 14% and 13% were unemployed, low income earners and skilled workers, respectively. However no occupation was spared. The commonest clinical feature was fever (84%). Headache (76%), malaise and body aches (68%), diarrhoea (58%), lymphadenopathy (28%), oral thrush (26%), herpes zoster skin rash (25%) pallor (6%), jaundice (2%) and coma (2%) also occurred in the patients. The duration of symptoms at presentation ranged from 2 days to 12 months. The sub-group with malaria and HIV co-infection had a mean (±SD) malaria parasite density of 6505.83 ± 18172.37 parasites/ul with a range of 400 to 213000 parasites/ul. The malaria only category had a mean (±SD) parasite density count of 3335.69±6547.68 parasites/ul with a range of 270 to 36740 parasites/ul. The difference in mean (±SD) between the two groups was statistically significant (F=7.016, p=0.008). The mean CD4+ T-lymphocyte counts of Mps/HIV +ve, mps only and healthy controls were 332.67, 741.96 and 887.57cells/ul respectively. The difference in mean values between the groups was statistically significant (F=4.352, df =333 and p=0.000). Patients with CD4 count ≥ 500cells/ul (21%) had malaria parasite density of 1460.88 parasites/ul, those with 200-499cells/ul (44%), had 2662.31parasites/ul whereas those with < 200cells/ul (35%) had a mean density of 14373.23cells/ul (F=8.93, p=0.000209). Therapeutic response using ABC drugs was better in the malaria only patients (91.2%) as compared with Mps/HIV +ve (85%) patients (p=0.000). It was concluded that malaria parasitaemia in HIV varied with different levels of immunity related to HIV disease stage as signified by CD4 counts and that therapeutic response to anti-malaria was higher in those withou