Recognizing the right to self-determination of Indigenous Peoples is essential to improving the state of community-based primary healthcare (CBPHC) of First Nations in Canada. Understanding communities' priorities and local health agendas is critical for primary healthcare transformation. We used a community-based participatory research approach to engage key partners: Nanaandawewiwgamig, the First Nations Health and Social Secretariat of Manitoba, and eight First Nation communities. Community-based research assistants conducted 183 in-depth interviews in their respective First Nations. Key themes that emerged from these interviews include primary prevention focused on health and social determinants; an integrated healthcare system providing access to both Western medicine and First Nations traditional health knowledge; infrastructure improvement; youth engagement; healthcare leadership; investing in community-based human resources; and promoting culturally respectful, responsive, and geographically sensitive and outcomes-oriented care. Policy approaches could implement some local priorities with direct impact on healthcare, while other social determinants could create indirect, albeit critical, conditions for health and healthcare changes over time.