Objectives. We assessed agreement of reported gender of sex partners in 2 statewide HIV databases linked by client identifiers. Methods. Counseling, testing, and referral (CTR) records on all men aged 18 to 30 years who tested newly positive for HIV in North Carolina between 2000 and 2005 were matched to data abstracted from partner counseling and referral services (PCRS) records. We compared client-reported gender of sex partners at the time of testing (CTR records) with those reported during postdiagnosis partner notification (PCRS records). Results. PCRS records appeared to be a more complete measure of the gender of sex partners. Of the 212 men who told their HIV test counselor that they had only had female sex partner or partners in their lifetime, 62 (29.2%) provided contact information for male sex partner(s) during partner notification. Conclusions. During the test counseling risk assessment, many men did not fully report the gender of their sex partners; this suggests that CTR data may not fully capture clients' risk behaviors.