Mozambique has one of the world's highest burdens of HIV infection. Despite the increase in HIV-testing services throughout the country, the uptake has been low. To identify barriers to HIV testing we conducted a study in six rural districts in Zamb├ęzia Province. We recruited a total of 124 men and women from the community through purposeful sampling to participate in gender-specific focus group discussions about barriers to HIV testing. The participants noted three main barriers to HIV testing: 1) poor conduct by clinicians, including intentional disclosure of patients' HIV status to other community members; 2) unintentional disclosure of patients' HIV status through clinical practices; and, 3) a widespread fatalistic belief that HIV infection will result in death, particularly given poor access to adequate food. Improving quality and confidentiality within clinical service delivery, coupled with the introduction of food-supplement programmes should increase people's willingness to test and remain in care for HIV disease.