Associating the health-related records and transactions of patients with their numerous “identities” as they interact with different healthcare providers, payers, pharmacy benefit managers and other entities is an expensive and complex problem. With many years of experience addressing this issue in different healthcare systems and Health Information Exchanges (HIEs), it is apparent that there is now a compelling and relatively straightforward technical solution for this problem. Presented here is a broadly feasible and technically compelling argument for a blockchain-based approach to addressing these issues. At the same time, challenges ahead and potential strategies to address them are discussed.