Background: HIV laboratory surveillance data (reported CD4 count and viral load results) are often used to identify persons living with HIV/AIDS (PLWHA) who are out of HIV care, but many health departments lack resources to investigate all cases missing recent data. A risk scoring tool could identify cases most likely to benefit from HIV care re-linkage efforts. Methodology: We derived and internally validated a risk scoring tool using data from public health investigations of HIV cases in King County, WA that had no lab results reported to our health department for ≥12 months prior to 4/30/2012. We separately derived and validated risk scores for 1) out-migration or death (“Gone”) and 2) currently residing in area and contactable (“In Area, Contactable”). The investigation protocol included queries to a governmenta records database, medical records searches, calls to HIV medical and social service providers, and calls and letters to PLWHA. We randomly divided the dataset in half, and used one dataset for risk score development and the other for validation. Results: Among 5,708 diagnosed PLWHA in King County, 1128 (20%) had no lab reported for ≥12 months prior to 4/30/2012. Of these, 413 (37%) were determined through case investigation to have out-migrated or died, 219 (19%) were in the area and successfully contacted, 168 (15%) were in the area but were not contacted because new lab results were reported before contact was attempted, and 328 (29%) were not conclusively determined to be out of area and were not contactable. The final model for each risk score included 3 variables: years since last laboratory report (<5, 5-9, >9), county of residence at the time of HIV diagnosis (King or not), and years of age at the time of ascertainment of gap in laboratory results (≤40, 41-65, >65). The “Gone” score had modest discriminatory accuracy [area under the receiver-operator characteristic (ROC) curve = 0.65] as did the In Area, Contactable” score (AUC=0.72). Internal validation demonstrated similar predictive ability of both risk scores in the validation group. Conclusions: We found that a combination of 3 variables available in standard HIV surveillance predicted the likelihood that a PLWHA was residing locally and contactable. Although the accuracy of this score requires external validation, choosing not to investigate cases with “In Area, Contactable” scores of <3 would allow health departments to avoid approximately one-third of all investigations while missing only 5% of contactable persons.