Air pollution and greenness are environmental determinants of mental health, though existing evidence typically considers each exposure in isolation. We evaluated relationships between co-occurring air pollution and greenspace levels and depression and anxiety. We estimated cross-sectional associations among 9015 Gulf Long-term Follow-up Study participants living in the southeastern U.S. who completed the Patient Health Questionnaire-9 (depression: score ≥ 10) and Generalized Anxiety Disorder Questionnaire-7 (anxiety: score ≥ 10). Participant residential addresses were linked to annual average concentrations of particulate matter (1 km PM) and nitrogen dioxide (1 km NO), as well as satellite-based greenness (2 km Enhanced Vegetation Index (EVI)). We used adjusted log-binomial regression to estimate prevalence ratios (PR) and 95 % confidence intervals (CI) for associations between exposures (quartiles) and depression and anxiety. In mutually adjusted models (simultaneously modeling PM, NO, and EVI), the highest quartile of PM was associated with increased prevalence of depression (PR = 1.17, 95 % CI: 1.06-1.29), whereas the highest quartile of greenness was inversely associated with depression (PR = 0.89, 95 % CI: 0.80-0.99). Joint exposure to greenness mitigated the impact of PM on depression (PR = 1.20, 95 % CI: 1.06-1.36; PR = 0.98, 95 % CI: 0.83-1.16) and anxiety (PR = 1.10, 95 % CI: 1.00-1.22; PR = 0.95, 95 % CI: 0.83-1.09) overall and in subgroup analyses. Observed associations were stronger in urbanized areas and among nonwhite participants, and varied by neighborhood deprivation. NO exposure was not independently associated with depression or anxiety in this population. Relationships between PM, greenness, and depression were strongest in the presence of characteristics that are highly correlated with lower socioeconomic status, underscoring the need to consider mental health as an environmental justice issue.