To find lower and upper bounds of HIV prevalence in Malawi under mild and intuitive assumptions to assess the importance of the refusal issue in the estimation of HIV prevalence. Methods: We derive bounds based on the following two key assumptions: (i) Among those who have never taken an HIV test before, those who refuse to take an HIV test (hereafter “refusers”) have at least as much risk to be HIV positive as those who participate in the HIV test, and (ii) among the refusers, those who have a prior testing experience are at least as likely to be HIV positive as those who have no prior experience. We compute the bounds using the Malawi Demographic and Health Survey and a longitudinal data set with a HIV testing component collected in the Malawi Diffusion and Ideational Change Project disaggregated by the sex, urban/rural areas, and three regions of Malawi. Findings: The bounds of HIV prevalence vary substantially across geographic and demographic groups. In particular, the bounds for males are tighter than those for females and the bounds for the Northern region are also tighter than those for other regions. There is no substantial difference in the width of bounds between the rural and urban populations. Conclusion: Bounds are useful for assessing the influence of refusal bias without the need for strong assumptions. Refusal issue is less of a concern if bounds are tight. However, when bounds are wide, refusal issue may be important.