Global warming and the rise in extreme heat days elevate the risk of heat-related mortalities, particularly in cities due to the Urban Heat Island (UHI) effect and vulnerabilities tied to housing, exposure, and health conditions. City planners can mitigate these effects through urban adaptive actions. UHI mitigation, however, needs to balance several goals: strategies that maximize temperature reduction or minimize their impacts may not be best for cost effectiveness, carbon emissions, environmental amenities, health impacts, or distributional outcomes. Here, we implement a multi-objective robust decision-making tool for heat mitigation—the City-Heat Equity Adaptation Tool (City-HEAT)—to identify potential heat mitigation pathways at neighborhood scales. We find that more expensive pathways tend to have larger benefits in reducing heat-related deaths, but that these pathways sometimes underperform against other alternatives on reducing inequality in mortality outcomes. Pathways that focus on tree planting, a popular and powerful tool for UHI reduction, were found to be expensive and less effective at reducing health disparities than more diversified pathways, if no specific measures are taken to target tree distribution for distributional benefit. The generated pathways can reduce Baltimore’s heat related mortality by 81–670 deaths in the next 50 years, considering different investment plans in the city’s neighborhoods. We also find that these results are relatively insensitive to expectations for future warming: pathways designed for high warming rates are similar to those designed for low warming rates, suggesting that general strategies for UHI mitigation can be robust to climate uncertainties.