We compare methods for linking public health surveillance data to inform public health department programs and activities. Public health surveillance data are often used to identify health disparities and target prevention efforts. In order to improve the efficiency and effectiveness of programs relying on surveillance data, these data are typically linked with external data sources, often in the absence of a common person identifier. Despite the widespread use of data matching techniques throughout public health, strikingly little information is available to guide the choice of record linkage algorithm. We used simulation studies to compare the precision, recall, and computational performance of six record linkage algorithms (an exact match, three deterministic algorithms, fastLink – an implementation of the Fellegi-Sunter algorithm, and beta record linkage – a probabilistic matching algorithm that uses Gibbs Sampler) that are commonly used link public health surveillance data with external data sources or the purpose of public health action. Additionally, we compare the recall and precision of each algorithm in a real data example using HIV and STD surveillance data.