Objective: To investigate the potential of record linkage between the Australian Bureau of Statistics (ABS) mortality data and the NSW Admitted Patient Data Collection (APDC) to improve reporting of deaths among Aboriginal and Torres Strait Islander peoples. Methods: ABS mortality data for 2002 to 2006 were linked with APDC records for 2001 to 2006. Six algorithms were developed to enumerate deaths. Possible biases by age, sex and geographic remoteness were investigated. Results: Levels of reporting ranged from baseline reporting on the ABS mortality data to the largest enhancement with the ‘ever reported as Aboriginal or Torres Strait Islander’ algorithm. Enhancement was more likely in females, older people and residents of major cities. Conclusions: Data linkage substantially improved reporting of Aboriginal and Torres Strait Islander deaths. An algorithm that includes both the number of APDC records and the number of facilities reporting a person as Aboriginal or Torres Strait Islander was considered most promising. Implications: Inclusion of other datasets in the enhancement process is warranted to further improve reporting and address possible bias produced by using APDC records only. Further work should take into account the possibility that a person may be falsely reported as Aboriginal or Torres Strait Islander or not reported in either hospital or death records.