This study explored perceptions and care-seeking practices for HIV testing and contraception in order to obtain data for designing effective interventions to increase contraception among HIV-positive women. A triangulation of methods (household survey, focus group discussions and key informant interviews) were conducted in Wakiso district, central Uganda from January to April 2009. Results show that a majority of women, 2062/2896 (71.2%) would like to have an HIV test, while access to antiretroviral therapy (ART) was low at 237/879 (27%). Of the women who were on ART, 133/266 (50.0%) could not use contraception due to negative perceptions that a combination of ART and contraceptives would weaken them, as these drugs were perceived to be ‘strong’. Fear of side-effects for contraceptives and resistance from spouses were other main reasons. Constraints to HIV testing included fear of clients knowing their own HIV status and fear of their spouses’ reactions to the test results. Private midwives were identified as a potential outlet for delivering contraception to HIV-positive women.