Background: The association between baseline seropositivity to human adenovirus (HAdV) type 5 and increased HIV acquisition in the Step HIV Vaccine Study has raised questions concerning frequency of acquired and/or persistent Adenovirus infections among adults at high risk of HIV-1 infection. Methodology: To evaluate the frequency and pattern of HAdV shedding from the lower GI tract, we retrospectively tested rectal swabs for HAdVs in a cohort of 20 HSV-2 positive HIV-positive Peruvian men who have sex with men (MSM) undergoing rectal swabbing three times/week for 18 consecutive weeks, in a prospective study of HSV-2 suppression in HIV infection. Viral DNA was extracted and amplified using a sensitive multiplex PCR assay that detects all currently recognized HAdV types. Molecular typing of viruses was performed on selected samples by hexon gene sequencing. Baseline neutralizing antibody titers to HAdVs 25, 226, 235 and 248 were also assessed. Principal Findings: 15/20 individuals had HAdV detected during follow up. The median frequency of HAdV detection was 30% of samples (range 2.0% to 64.7%). HAdV shedding typically occurred on consecutive days in clustered episodes lasting a median of 4 days (range 1 to 9 days) separated by periods without shedding, suggesting frequent new infections or reactivation of latent infections over time. 8 of the 15 shedders had more than one type detected in follow-up. 20 HAdV types from species B, C, and D were identified, including HAdV-5, 226 and 248, HAdV types under development as potential vaccine candidates. 14/20 subjects were seropositive for HAdV-5; 15/20 for HAdV-26; 3/20 for HAdV-35; and 2/20 for HAdV-48. HAdV shedding did not correlate with CD4 count, plasma HIV-1 viral load, or titers to HAdV-5 or HAdV-35. The sole individual with HAdV-5 shedding was HAdV-5 seropositive. Conclusions: HAdV shedding was highly prevalent and diverse, including types presently under consideration as HIV vaccine vectors. Subclinical HAdV infection of the GI tract is common among MSM in Peru; the prevalence of HAdV in the enteric tract should be evaluated in other populations. The association between ongoing recent enteric HAdV and the immune response to recombinant HAdV vaccines should be evaluated.