Objective: To acquire a deepened understanding of how stigma in healthcare affects health-seeking behaviors of same-sex practising men in Tanzania. Methods: In-depth interviews with 12 men were conducted in Dar es Salaam, 2012. Data were interpreted through qualitative content analysis. Results: Narratives revealed that men's healthcare perceptions were shaped by previous encounters, rumors in gay community, norms, and legislation around homosexuality. Fears of exposure aggravated men's possibilities of giving full anamnesis and detached them from formal healthcare services. Conclusions: Stigma in healthcare might lead to severe public health problems due to perceived exclusion from the health system by sexual minorities.