(1) Background: Genomic precision medicine (PM) utilises people’s genomic data to inform the delivery of preventive and therapeutic health care. PM has not been well-established for use with people of Aboriginal and Torres Strait Islander ancestry due to the paucity of genomic data from these communities. We report the development of a new protocol using co-design methods to enhance the potential use of PM for Aboriginal Australians. (2) Methods: This iterative qualitative study consists of five main phases. Phase-I will ensure appropriate governance of the project and establishment of a Project Advisory Committee. Following an initial consultation with the Aboriginal community, Phase-II will invite community members to participate in co-design workshops. In Phase-III, the Chief Investigators will participate in co-design workshops and document generated ideas. The notes shall be analysed thematically in Phase-IV with Aboriginal community representatives, and the summary will be disseminated to the communities. In Phase-V, we will evaluate the co-design process and adapt our protocol for the use in partnership with other communities. (3) Discussion: This study protocol represents a crucial first step to ensure that PM research is relevant and acceptable to Aboriginal Australians. Without fair access to PM, the gap in health outcome between Aboriginal and non-Aboriginal Australians will continue to widen.