The COVID-19 pandemic, coupled with the “infodemic” of misinformation, meant First Nations peoples in Australia’s Northern Territory were hearing “the wrong story” about COVID-19 vaccines. In March 2021, when the Australian government offered COVID-19 vaccines to First Nations adults there was no vaccine information designed with, or for, the priority group. To address this gap, we conducted a Participatory Action Research project in which First Nations leaders collaborated with White clinicians, communication researchers and practitioners to co-design 16 COVID-19 vaccine videos presented by First Nations leaders who spoke 9 languages. Our approach was guided by Critical Race Theory and decolonising processes including Freirean pedagogy. Data included interviews and social media analytics. Videos, mainly distributed by Facebook, were valued by the target audience because trusted leaders delivered information in a culturally safe manner and the message did not attempt to enforce vaccination but instead provided information to sovereign individuals to make an informed choice. The co-design production process was found to be as important as the video outputs. The co-design allowed for knowledge exchange which led to video presenters becoming vaccine champions and clinicians developing a deeper understanding of vaccine hesitancy. Social media data revealed that: sponsored Facebook posts have the largest reach; videos shared on a government branded YouTube page had very low impact; the popularity of videos was not in proportion to the number of language speakers and there is value in reposting content on Facebook. Effective communication during a health crisis such as the COVID-19 pandemic requires more than a direct translation of a script written by health professionals; it involves relationships of reciprocity and a decolonised approach to resource production which centres First Nations priorities and values.