Rates of anxiety and depression among adolescents are rising globally. Exposure to greenness is recognised as a determinant of mental health but little is known about its impacts on adolescent mental health on a population scale. We examined the prospective association between residential greenness from birth to age 12 and subsequent health-care contacts for mood or anxiety disorders during adolescence. We conducted a population-scale longitudinal study using linked health, administrative data, and environmental measures for 831,957 individuals in the Ontario Mental Health and Intersectionality Data Surveillance Cohort within a Trusted Research Environment (ICES). The outcome was diagnosis-specific mental health-related service use for mood or anxiety disorders. Exposure was defined as residential greenness within a 250-metre buffer around each participant’s postcode centroid from birth to age 12. Associations between exposure to greenness and mood or anxiety-related service use were estimated using fully adjusted multivariable Cox regression models. In our cohort, 51.3% were female and 422,227 individuals had at least one mood- or anxiety-related service use. Mean greenness exposure was 0.12 (range 0–0.74). Greater exposure to greenness was associated with lower risk of mood or anxiety service use. A statistically significant U-shaped relationship was observed, with the highest risk in quintile 3 (HR 1.09, 95% CI 1.08–1.10) compared with the greenest quintile. Childhood exposure to greenness appears protective against later mood and anxiety-related service use and nonlinear effects warrant further investigation. This evidence can be used by policy and practice for the design of interventions.