BACKGROUND: Provision of HIV prevention and sexual and reproductive health services in Zambia is largely characterized by discrete service provision with weak client referral and linkage. The literature reveals gaps in the continuity of care for HIV and sexual and reproductive health. This study assessed whether improved service delivery models increased the uptake and cost-effectiveness of HIV and sexual and reproductive health services. METHODS: Adult clients 18+ years of age accessing family planning (females), HIV testing and counseling (females and males), and male circumcision services (males) were recruited, enrolled and individually randomized to one of three study arms: 1) the standard model of service provision at the entry point (N = 1319); 2) an enhanced counseling and referral to add-on service with follow-up (N = 1323); and 3) the components of study arm two, with the additional offer of an escort (N = 1321). Interviews were conducted with the same clients at baseline, six weeks and six months. Uptake of services for HIV, family planning, male circumcision, and cervical cancer screening at six weeks and six months were the primary endpoints. Pairwise chi-square and multivariable logistic regression statistical tests assessed differences across study arms, which were also assessed for incremental cost-efficiency and cost-effectiveness. RESULTS: A total of 3963 clients, 1920 males and 2043 females, were enrolled; 82 % of participants at six weeks were tracked and 81 % at six months; follow-up rates did not vary significantly by study arm. The odds of clients accessing HIV testing and counseling, cervical cancer screening services among females, and circumcision services among males varied significantly by study arm at six weeks and six months; less consistent findings were observed for HIV care and treatment. Client uptake of family planning services did not vary significantly by study arm. Integrated services were found to be more efficiently provided than vertical service provision; the cost-effectiveness for HIV/AIDS and cervical cancer was high in the enhanced service models. CONCLUSIONS: Study results provide evidence for increasing the linkages and integration of a selection of HIV and sexual and reproductive health services. The study provided cost-effective service delivery models that enhanced the likelihood of clients accessing some additional needed health services. TRIAL REGISTRATION: ISRCTN84228514 Retrospectively registered. The study was retrospectively registered in the ISRCTN clinical trials registry on 06 October 2015. The first recruitment of participants occurred on 17 December 2013.