Genital Chlamydia trachomatis (CT) and Neisseria gonorrhoeae (GC) are reportable diseases in the U.S. Air Force. Base-level personnel enter laboratory-confirmed cases into the Air Force Reportable Events Surveillance System (AFRESS). To examine completeness and timeliness of CT and GC reporting, we compared laboratory and AFRESS records collected between 2000 and 2005. We used joinpoint regression analysis to identify trends in reporting over time. Of 23,118 CT laboratory-confirmed cases, 74.0% were reported into AFRESS; of 1,897 GC cases, 57.5% were reported. CT reporting completeness increased through 2003, but declined afterward; completeness of GC reporting steadily declined throughout the study. The median time between collection and reporting dates was 12.0 days and 13.5 days for CT and GC, respectively. Timeliness of CT reporting improved until mid-2004, after which it sharply declined; GC reporting timeliness declined throughout the study. Monitoring data, training personnel, and adopting an electronic reporting system may improve data quality.