Adenoviruses are common pathogens that often are associated with respiratory and gastrointestinal illness and/or conjunctivitis in young persons. Adenovirus serotypes 4 and 7 have caused outbreaks of self-limited febrile respiratory illness in young adults in basic military training. During the 1950s and 1960s, up to 10% of recruits were infected with adenovirus, and these pathogens were responsible for approximately 90% of pneumonia hospitalizations. Beginning in 1971, all military recruits received oral, live, enteric-coated vaccines that were licensed by the Food and Drug Administration as safe and effective in preventing illness from adenovirus serotypes 4 and 7. In 1996, the sole manufacturer ceased production of adenoviral vaccines and, as supplies dwindled during the next few years, outbreaks of adenoviral respiratory illness reemerged in military settings. Since 1999, approximately 10%-12% of all recruits have become ill with adenovirus infection in basic training, similar to the prevaccine era. This report describes the first two deaths probably associated with adenovirus infection identified in military recruits since the vaccines became unavailable. The military has requested proposals for a new adenovirus vaccine manufacturer; however, these deaths suggest that efforts by policymakers and pharmaceutical companies to reestablish adenoviral vaccine production should be intensified.