We describe the same-sex partnerships and sexual risk behavior of men attending sexually transmitted infection (STI) clinics in Mumbai, India. The HIV prevalence among 2,381 men sampled was 14%; 62% had a documented STI. Almost all men reported sex with women; additionally, 13% also reported having sex with other men, 13% reported sex with Hijras (male-to-female transgenders), and 11% had sex with all 3 genders. Men who had sex with men and/or Hijras as well as women, reported having greater numbers of partners, including female sex workers (FSW), and were more likely to engage in insertive anal and oral sex with women. The prevalence of HIV was higher among men having sex with Hijras (14%) or with all 3 genders (13%) than among men having sex with men and women (8%). A high proportion of men who attend STI clinics in Mumbai are behaviorally bi- or tri-sexual and have multiple partners with whom they engage in risky sex. STI/HIV prevention programs should not assume that men only have sex with women.