Introduction Preventable diseases like measles and mumps are occurring with increasing frequency in the U.S. despite the availability of an effective vaccine. Given concern that an outbreak may occur among military recruits, we compared serologic evidence of immunity to measles, mumps, and rubella among military recruits with known herd immunity thresholds and determined whether the current Department of Defense policy of presuming mumps immunity based on measles and rubella titers is reliable. Methods Serum antibody levels for measles, mumps, and rubella were obtained from all new recruits upon arrival at Joint Base San Antonio-Lackland, Texas, from 25 April 2013 through 24 April 2014. Seroprevalence of each disease was assessed by age and sex, and concordance between mumps titers and measles and rubella titers was calculated. Data analysis was performed in 2014-2015. Results Among 32,502 recruits, seroprevalences for measles, mumps, and rubella antibodies were 81.6%, 80.3%, and 82.1%, respectively. Of the 22,878 recruits seropositive for both measles and rubella antibodies, 87.7% were also seropositive for mumps. Conclusions Seroprevalences for measles, mumps, and rubella antibodies among a large cohort of recruits entering U.S. Air Force basic training were generally lower than levels required to maintain herd immunity. In order to reduce the incidence of mumps infections, the Department of Defense should consider obtaining antibody titers for measles, mumps, and rubella and vaccinating all individuals susceptible to one or more of the viruses.