Objectives: Inequalities between Indigenous and non-Indigenous peoples in Canada persist. Despite the growth of Indigenous populations in urban settings, information on their health is scarce. The objective of this study is to assess the association between experience of discrimination by healthcare providers and having unmet health needs within the Indigenous population of Toronto. Methods: The Our Health Counts Toronto (OHCT) database was generated using respondent-driven sampling (RDS) to recruit 917 self-identified Indigenous adults within Toronto for a comprehensive health assessment survey. This cross-sectional study draws on information from 836 OHCT participants with responses to all study variables. Odds ratios and 95% confidence intervals were estimated to examine the relationship between lifetime experience of discrimination by a healthcare provider and having an unmet health need in the 12 months prior to the study. Stratified analysis was conducted to understand how information on access to primary care and socio-demographic factors influenced this relationship. Results: The RDS-adjusted prevalence of discrimination by a healthcare provider was 28.5% (95% CI 20.4–36.5) and of unmet health needs was 27.3% (95% CI 19.1–35.5). Discrimination by a healthcare provider was positively associated with unmet health needs (OR 3.1, 95% CI 1.3–7.3). Conclusion: This analysis provides new evidence linking discrimination in healthcare settings to disparities in healthcare access among urban Indigenous people, reinforcing existing recommendations regarding Indigenous cultural safety training for healthcare providers. Our study further demonstrates Our Health Counts methodologies, which employ robust community partnerships and RDS to address gaps in health information for urban Indigenous populations.