Health care professionals’ (HCPs) notions about gender may influence the provision and quality of care. If care-seeking men are met by HCPs holding idealized and stereotypical notions of masculinity, this could reinforce barriers to adequate care. This study explored notions about men and masculinities among HCPs working with men’s sexual health in Sweden. Focus group interviews with 35 HCPs from primary health and sexual health clinics were analyzed using qualitative content analysis. The analysis resulted in three descriptive themes: (a) Contradictory masculinity—elusive but clear. Notions of masculinity as a phenomenon or concept were elusive, but masculine and un-masculine traits, behaviors, and qualities were clear. (b) Sexual health care is a social place where men and masculinities can be challenging. Male patients were associated with unwanted sexual tensions. Masculinity could challenge professionality. Seeking sexual health care was perceived as doing un-masculinity. (c) Regarding masculinity as irrelevant—a difficult ambition to achieve. Participants strived for gender-neutrality by regarding patients as humans, individuals, or patients rather than as men and masculine. The analysis also identified a theme of meaning: Notions of masculinity are situated relationally. HCPs situate masculinity in real and hypothetical relationships. Romantic and sexual preferences were used to define preferred masculinity. This study identified themes that showed how HCPs balanced professional and private notions of men and masculinity in their patient encounters. Increased gender awareness and training are needed to professionalize the management of gendered notions in encounters with men who seek care for sexual health problems.