US military personnel are routinely screened for HIV infection. Herpes simplex virus type 2 (HSV-2) is a risk factor for HIV acquisition. To determine the association between HSV-2 and HIV, a matched case-control study was conducted among US Army and Air Force service members with incident HIV infections (cases) randomly matched with two HIV-uninfected service members (controls) between 2000 and 2004. HSV-2 prevalence was significantly higher among cases (30.3%, 138/456) than among controls (9.7%, 88/912, P < 0.001). HSV-2 was strongly associated with HIV in univariate (odds ratio [OR] = 4.2, 95% confidence interval [CI] = 3.1-5.8) and multiple analyses (adjusted [OR] = 3.9, 95% CI = 2.8-5.6). The population attributable risk percentage of HIV infection due to HSV-2 was 23%. Identifying HSV-2 infections may afford the opportunity to provide targeted behavioural interventions that could decrease the incidence of HIV infections in the US military population; further studies are needed.