Mounting evidence indicates that genital HSV-2 infection may increase susceptibility to HIV infection and that co-infection may increase infectiousness. Accordingly, antiviral treatment of people with HSV-2 may mitigate the incidence of HIV in populations where both pathogens occur. To better understand the epidemiological synergy between HIV and HSV-2, we formulate a deterministic compartmental model that describes the transmission dynamics of these pathogens. Unlike earlier models, ours incorporates gender and heterogeneous mixing between activity groups. We derive explicit expressions for the reproduction numbers of HSV-2 and HIV, as well as the invasion reproduction numbers via next generation matrices. A qualitative analysis of the system includes the local and global behavior of the model. Simulations reinforce these analytical results and demonstrate epidemiological synergy between HSV-2 and HIV. In particular, numerical results show that HSV-2 favors the invasion of HIV, may dramatically increase the peak as well as reducing the time-to-peak of HIV prevalence, and almost certainly has exacerbated HIV epidemics. The potential population-level impact of HSV-2 on HIV is demonstrated by calculating the fraction of HIV infections attributable to HSV-2 and the difference between HIV prevalence in the presence and absence of HSV-2. The potential impact of treating people with HSV-2 on HIV control is demonstrated by comparing HIV prevalence with and without HSV-2 therapy. Most importantly, we illustrate that the aforementioned aspects of the population dynamics can be significantly influenced by the sexual structure of the population.