We describe predictors of first follow-up testing for concordant negative and discordant couples seeking joint voluntary HIV counseling and testing in Ndola, Zambia, where cohabiting couples account for an estimated two-thirds of incident HIV infections.