An algorithm was developed that identifies patients with new diagnoses of HIV infection by the use of electronic health records. It was based on the sequence of HIV diagnostic tests, entry of ICD-9-CM diagnostic codes, and measurement of HIV-1 plasma RNA levels in persons undergoing HIV testing from 2006 to 2012 at four large urban Veterans Health Administration (VHA) facilities. Source data were obtained from the VHA National Corporate Data Warehouse. Chart review was done by a single trained abstractor to validate site-level data regarding new diagnoses. We identified 1,153 patients as having a positive HIV diagnostic test within the VHA. Of these, 57% were determined to have prior knowledge of their HIV status from testing at non-VHA facilities. An algorithm based on the sequence and results of available laboratory tests and ICD-9-CM entries identified new HIV diagnoses with a sensitivity of 83%, specificity of 86%, positive predictive value of 85%, and negative predictive value of 90%. There were no meaningful demographic or clinical differences between newly diagnosed patients who were correctly or incorrectly classified by the algorithm. We have validated a method to identify cases of new diagnosis of HIV infection in large administrative datasets. This method, which has a sensitivity of 83%, specificity of 86%, positive predictive value of 85%, and negative predictive value of 90% can be used in analyses of the epidemiology of newly diagnosed HIV infection.