Objective: To acquire a deepened understanding of how stigma in healthcare affects health-seeking behaviours of same-sex practising men in Tanzania. Methods: In-depth interviews with twelve 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, rumours 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.