Abstract Background Plasmodium falciparum and HIV-1 infection cause substantial morbidity and mortality in sub-Saharan Africa. Increasing evidence suggests these two pathogens interact negatively when infecting the same individual. Methods A cross-sectional study among HIV-1 infected and uninfected populations was recruited in Mocuba and Maputo, Mozambique to determine the prevalence of sub-clinical malarial parasitaemia using light microscopy and a nested PCR assay. Results The prevalence of sub-clinical P. falciparum parasitaemia was low in Maputo, whether determined by microscopy (0.4%) or PCR (1.9%), but substantially higher in Mocuba (7.6 and 14.7%, respectively). Nested PCR detected nearly 70% more cases of sub-clinical parasitaemia than microscopy, but differences occur by locality. HIV-1 infected persons were more likely to be sub-clinically parasitaemic than HIV-1 uninfected individuals recruited from the same geographic areas. Trimethoprim-sulphamethoxazole use did not substantially reduce sub-clinical parasitaemia. Conclusions Dried blood spots are a convenient and sensitive technique for detecting sub-clinical infection with P. falciparum by nested PCR. Prevalence of P. falciparum is substantially lower in Maputo where malaria control programmes have been more active than in the rural town of Mocuba. In Mocuba, among those presenting for HIV-1 counseling and testing, the prevalence of P. falciparum is substantially higher in those who test positive for HIV-1 than those without HIV-1 infection. The clinical implications of sub-clinical P. falciparum infection among HIV-1 infected persons warrant additional study.