Background: While co-design offers potential for equitably engaging First Nations Australians in findings solutions to redressing prevailing disparities, appropriate applications of co-design must align with First Nations Australians’ culture, values, and worldviews. To achieve this, robust, culturally grounded, and First Nations-determined principles and practices to guide co-design approaches are required. Aims: This project aimed to develop a set of key principles and best practices for co-design in health with First Nations Australians. Methods: A First Nations Australian co-led team conducted a series of Online Yarning Circles (OYC) and individual Yarns with key stakeholders to guide development of key principles and best practice approaches for co-design with First Nations Australians. The Yarns were informed by the findings of a recently conducted comprehensive review, and a Collaborative Yarning Methodology was used to iteratively develop the principles and practices. Results: A total of 25 stakeholders participated in the Yarns, with 72% identifying as First Nations Australian. Analysis led to a set of six key principles and twenty-seven associated best practices for co-design in health with First Nations Australians. The principles were: First Nations leadership; Culturally grounded approach; Respect; Benefit to community; Inclusive partnerships; and Transparency and evaluation. Conclusions: Together, these principles and practices provide a valuable starting point for the future development of guidelines, toolkits, reporting standards, and evaluation criteria to guide applications of co-design with First Nations Australians.