To determine the completeness of reporting of human immunodeficiency virus (HIV) diagnoses to state surveillance systems, the authors used capture-recapture methods. The numbers of cases diagnosed in the areas were estimated using HIV diagnoses reported to nine surveillance programs by different sources (e.g., laboratories, health-care providers). To account for dependencies between reporting sources, the authors used log-linear models to estimate the number of cases that had been diagnosed but were not identified by any reporting sources. Completeness of reporting (observed cases/expected cases) was determined for two time frames: cases diagnosed within a 1-year period (from October 1, 2002, to September 30, 2003, for most US states) reported up to 6 months after that diagnosis period and cases diagnosed within a 6-month period reported up to 12 months after that diagnosis period. A total of 11,266 HIV diagnoses were reported for the 1-year period with 21,589 report documents. Completeness of reporting of HIV diagnoses was 76% (95% confidence interval: 66, 83) when allowing 6 months of reporting delay (range: 72–95%) and improved to 81% (95% confidence interval: 72, 88) with 12 months' follow-up. When reporting systems retain all relevant documents, capture-recapture is a feasible approach for assessing completeness of reporting of HIV diagnoses. Completeness should be measured by allowing 12-months' reporting delay.