BACKGROUND AND OBJECTIVES: Algorithms are often used to improve identification of Aboriginal Australians in linked data sets with inconsistent and incomplete recording of Aboriginal status. We compared how consistently some common algorithms identified family members, developed a new algorithm incorporating relatives' information, and assessed the effects of these algorithms on health estimates. METHODS: The sample was people born 1980-2011 recorded as Aboriginal at least once (or a relative) in four Western Australian data sets and their relatives (N = 156,407). A very inclusive approach, ever-Aboriginal (EA/EA+, where + denotes children's records incorporated), and two more specific approaches, multistage median (MSM/MSM+) and last record (LR/LR+), were chosen, along with the new algorithm (MSM+Family). RESULTS: Ever-Aboriginal (EA) categorized relatives the least consistently; 25% of parent-child triads had incongruent Aboriginal statuses with EA+, compared with only 9% with MSM+. With EA+, 14% of full siblings had different statuses compared with 8% for MSM+. EA produced the lowest estimates of the proportion of Aboriginal people with poor health outcomes. Using relatives' records reduced the number of uncategorized people and categorized as Aboriginal more people who had few records (e.g., no hospital admissions). CONCLUSION: When many data sets are linked, more specific algorithms select more representative Aboriginal samples and identify Aboriginality of relatives more consistently. Copyright © 2017 Elsevier Inc. All rights reserved.