In the United States 40% of HIV patients are lost to follow-up (LTFU) following linkage to HIV care and an estimated 30–61% of new HIV transmissions are attributed to this group. To characterize those LTFU and healthcare contacts they make, we retrospectively analyzed a large regional HIV cohort in Calgary, Canada, utilizing a province-wide electronic health record. Adults engaged in HIV care between January 2010 and August 2014 who had >12 months without HIV clinic contact were identified as LTFU. Of 1928 individuals engaged in care, 176 became LTFU with 64% having no healthcare contacts, 20% receiving HIV care elsewhere, and 16% making non-HIV healthcare contacts. Those LTFU making non-HIV healthcare contacts did so a median of six times (interquartile range 2–8), 76% attending emergency departments (ED). Compared to those retained in care, LTFU patients were younger (median age 43 versus 47 years), had lower CD4⁺cell counts (median 420 versus 500 × 10⁶/l) and more commonly resided outside of the centralized HIV clinic’s city (odds ratio 4.58) (all p < 0.01). Our finding that a majority of those LTFU did not make healthcare contacts suggests that community and HIV clinic-based relinkage programs are needed. For those LTFU who make healthcare contacts enhanced ED-based relinkage programs could engage a majority.