BACKGROUND: Studies have shown that couple HIV counseling and testing (CHCT) increased rates of sero-status disclosure and adoption of safer sexual behaviors with better linkage to treatment and care. However, current evidence suggests that new HIV infections are occurring among heterosexual couples in stable relationships where the majority of the individuals are not aware of their partner's serostatus. This study examined the predictors of CHCT uptake among married or cohabiting couples of Bukomero sub-county Kiboga district in Uganda. METHODS: This cross-sectional correlational study was conducted among 323 individuals who were either married or cohabiting, aged 18-49 years. Participants were enrolled from randomly selected households in Bukomero sub-county. Data were collected using an interviewer-administered questionnaire on socio-demographics, self-rating on awareness of CHCT benefits, couple discussion about HIV testing and CHCT practices. Couples were compared between those who had reported to have tested as a couple and those who had not. Binary logistic regression was performed to determine the adjusted odds ratio [aOR] and 95 % confidence intervals [CI] for CHCT uptake and the other independent variables. RESULTS: Of the participants 288 (89.2 %) reported to have ever taken an HIV test only 99 (34.4 %) did so as a couple. The predictors of testing for HIV as a couple were discussing CHCT with the partner (adjusted odds ratio 4.95[aOR], 95 % confidence interval [CI]:1.99-12.98; p < 0.001), awareness of CHCT benefits (aOR 3.23; 95 % CI 1.78-5.87; p < 0.001) and having time to test as a couple (aOR 2.61; 95 % CI 1.22-5.61; p < 0.05). CONCLUSION: Uptake of HIV counseling and testing among couples was low. Discussing CHCT with partner, awareness of CHCT benefits, and availability of time to test as a couple were predictive of CHCT uptake. Thus CHCT campaigns should emphasize communication and discussion of HIV counseling and testing among partners.