A signature feature of HIV infection is poor control of herpes virus infections, which reactivate from latency and cause opportunistic infections. While the general mechanism underlying this observation is deficient CD4+T-cell function, it is unknown whether increased severity of herpes virus infections is due primarily to poor immune control in latent or lytic sites of infection, or whether CD4+ immunodeficiency leads to more critical downstream deficits in humoral or cell-mediated immunologic responses. Here we compare genital shedding patterns of herpes simplex virus-2 (HSV-2) in 98 HIV infected and 98 HIV uninfected men matched on length of infection, HSV-1 serostatus and nationality. We demonstrate that high copy HSV-2 shedding is more frequent in HIV positive men, particularly in participants with CD4+ T-cell count <200/μL. Genital shedding is more frequent due to higher rate of shedding episodes, as well as a higher proportion of prolonged shedding episodes. Peak episode viral load was not found to differ between HIV infected and uninfected participants regardless of CD4+ T-cell count. We simulate a mathematical model which recapitulates these findings and identifies that rate of HSV-2 release from neural tissue increases, duration of mucosal cytolytic immune protection decreases, and cell-free viral lifespan increases in HIV infected participants. These results suggest that increased HSV-2 shedding in HIV infected persons may be caused by impaired immune function in both latent and lytic tissue compartments, with deficits in clearance of HSV-2 infected cells and extracellular virus.