Most people are concerned about climate change and want policymakers to address it. But how? To investigate which policy options are more versus less popular, with whom, and why, we collected data in four European countries on attitudes toward 16 policies: taxes, bans, regulations, and subsidies/spending. We argue that support for different policies should reflect perceptions of policies’ net costs, and that such perceptions are likely influenced by people’s political trust. We tested this expectation by randomly assigning survey respondents to read different versions of given policies and confirmed that individuals with low political trust, who are less supportive overall of most policies, are most sensitive to variation in implied costs. We argue this interaction effect is a previously untested implication of the influential theory that political trust operates as a heuristic, and it helps explain policies’ varying popularity, including the puzzle of why carbon taxes are highly unpopular.