Abstract Most work in planning focuses on tasks with stateindependent or even uniform action costs. However, supporting state-dependent action costs admits a more compact representation of many tasks. We investigate how to solve such tasks using heuristic search, with a focus on delete-relaxation heuristics. We first define a generalization of the additive heuristic hadd to such tasks and then discuss different ways of computing it via compilations to tasks with state-independent action costs and more directly by modifying the relaxed planning graph. We evaluate these approaches theoretically and present an implementation of hadd for planning with state-dependent action costs. To our knowledge, this gives rise to the first approach able to handle even the hardest instances of the combinatorial ACADEMIC A DVISING domain from the International Probabilistic Planning Competition (IPPC) 2014.