Free voluntary counseling and testing (VCT) has been available in Taiwan as a part of HIV surveillance and prevention program since 1999, but related data were seldom reported. We aimed to examine characteristics of individuals who attended anonymous client-initiated VCT service and factors associated with HIV infection. The study population consisted of clients at two large VCT sites located in northern and southern Taiwan in 2004- 2008. Information on socio-demographic factors and potential risk behaviors was obtained by a questionnaire. Of 5671 clients, 65.1% were younger than 30 years; 42.0%, 41.2%, and 16.8% were men who ever had sex with men (MSM), non-MSM males, and women with HIV seropositivity of 8.0%, 1.2%, and 1.5%, respectively. The proportion of clients who confirmed having a prior HIV test was 66.5% in MSM, followed by 43% in non-MSM, and 30.2% in women. Correlates of HIV seropositivity differed between genders: ever engaging in commercial sex, being married or less educated were associated with increased risks among women but not for men. Different independent predictors were revealed among three groups of clients by multivariable analyses: illicit drug use, anal sex behavior, sexual partner(s) with HIV, and one-night stand in MSM; injection drug use and history of sexually transmitted infections in non-MSM; and injection drug use, sexual partner(s) with HIV and trading sex in women. Of all three groups, illicit drug or injection drug use was associated with the highest risks among all independent predictors. In this population of VCT clients in Taiwan, risk profiles of HIV infection differed according to gender and MSM experience, and different prevention strategies are needed to target different risk groups. In women, risk factors related to low social demographic and relationship power deserves attention in planning future prevention efforts.