This paper explores low levels of women’s health service utilization for Sexually Transmitted Infections (STIs)in Nepal. We interviewed 120 women individually and 53 in focus groups. Predictors of lower utilisation were self-medication, consultation with faith healers, inadequate knowledge of STIs, beliefs about causes, fear, social taboos and stigmatisation, women’s secondary status, and presence of male health professionals. Results indicate the importance of people’s beliefs in their decisions about health care. Strategies to improve access to health services in Nepal should systematically investigate the role of all these factors to improve access to and utilisation of health services for STIs.