BACKGROUND: Heterosexual couples contribute to most new HIV infections in areas of generalized HIV epidemics in sub-Saharan Africa. After Couples' Voluntary HIV Counseling and Testing (CVCT), heterosexual concordant HIV negative couples (CNC) in cohabiting unions contribute to approximately 47% of residual new infections in couples. These infections are attributed to concurrent sexual partners, a key driver of the HIV epidemic in Zambia. METHODS/DESIGN: Ten Zambian government clinics in two of the largest cities were randomized in matched pairs to a Strengthening Our Vows (SOV) intervention or a Good Health Package (GHP) comparison arm. SOV addressed preventing HIV infection from concurrent partners and protecting spouses after exposures outside the relationship. GHP focused on handwashing; water chlorination; household deworming; and screening for hypertension, diabetes and schistosomiasis. CNC were referred from CVCT services in government clinics. Follow-up includes post-intervention questionnaires and outcome assessments through 60 months. Longitudinal outcomes of interest include self-report and laboratory markers of condomless sex with outside partners and reported sexual agreements. We present baseline characteristics and factors associated with study arm and reported risk using descriptive statistics. RESULTS: The mean age of men was 32 and 26 for women. On average, couples cohabited for 6 years and had 2 children. Baseline analyses demonstrated some failures of randomization by study arm which will be considered in future primary analyses of longitudinal data. An HIV/STI risk factor composite was not different in the two study arms. Almost one-quarter of couples had an HIV risk factor at baseline. DISCUSSION: In preparation for future biomedical and behavioral interventions in sub-Saharan Africa, it is critical to understand and decrease HIV risk within CNC.