Objective: To describe the challenges of obtaining state and nationally held data for linkage to a non-government national clinical registry. Methods: We reviewed processes negotiated to achieve linkage between the Australian Stroke Clinical Registry (AuSCR), the National Death Index, and state held hospital data. Minutes from working group meetings, national workshop meetings, and documented communications with health department staff were reviewed and summarised. Results: Time from first application to receipt of data was more than two years for most state data-sets. Several challenges were unique to linkages involving identifiable data from a non-government clinical registry. Concerns about consent, the re-identification of data, duality of data custodian roles and data ownership were raised. Requirements involved the development of data flow methods, separating roles and multiple governance and ethics approvals. Approval to link death data presented the fewest barriers. Conclusion: To our knowledge, this is the first time in Australia that person-level data from a clinical quality registry has been linked to hospital and mortality data across multiple Australian jurisdictions. Implications for Public Health: The administrative load of obtaining linked data makes projects such as this burdensome but not impossible. An improved national centralised strategy for data linkage in Australia is urgently needed.