Behavior change communication often focuses on individual-level variables such as knowledge, perceived risk, self-efficacy, and behavior. A growing body of evidence suggests, however, that structural interventions to change the policy environment and environmental interventions designed to modify the physical and social environment further bolster impact. Little is known about the cost-effectiveness of such comprehensive intervention programs. In this study we use standard cost analysis methods to examine the incremental cost-effectiveness of two such interventions conducted in the Dominican Republic in sex establishments. In Santo Domingo the intervention was environmental; in Puerto Plata it was both environmental and structural (levying financial sanctions on sex establishment owners who failed to follow the intervention). The interventions in both sites included elements found in more conventional behavior change communication (BCC) programs (e.g., community mobilization, peer education, educational materials, promotional stickers). One key aim was to examine whether the addition of policy regulation was cost-effective. Data for the analysis were gleaned from structured behavioral questionnaires administered to female sex workers and their male regular paying partners in 41 sex establishments conducted pre- and post-intervention (1 year follow-up); data from HIV sentinel surveillance, STI screening results conducted for the intervention; and detailed cost data we collected. We estimated the number of HIV infections averted from each of the two intervention models and converted these estimates to the number of disability life years saved as compared with no intervention. One-way, two-way, three-way, and multivariate sensitivity analysis were conducted on model parameters. We examine a discount rate of 0%, 3% (base case), and 6% for future costs and benefits. The intervention conducted in Santo Domingo (community mobilization, promotional media, and interpersonal communication) was estimated to avert 64 HIV infections per 10,000 clients reached, and resulted in a cost per disability-adjusted life year (DALY) saved of $1,186. In Puerto Plata a policy/regulatory intervention was added, which resulted in 162 HIV infections averted per 10,000 clients reached, and yielded a cost per DALY saved of $457. Cost-effectiveness estimates were most correlated to the discount rate used and base rates of sexually transmitted infection (which affects the HIV transmission rate). Both intervention models resulted in cost-effective outcomes; however, the intervention that included policy regulation resulted in a substantially more cost-effective outcome.