Abstract Most of the key computational ideas in classical planning assume a simple planning language where action preconditions and goals are conjunctions of propositional atoms. This is to facilitate the definition and computation of heuristics for guiding the search for plans. In this work, however, we show that this modeling choice hides important structural information, resulting in poorer heuristics and weaker planning performance. To address this, we show how relaxed plan heuristics can be lifted to a variable-free first-order planning language, Functional STRIPS, where atomic formulas can involve arbitrary terms. The key idea is to regard the set of atoms that are reachable in a propositional layer of the relaxed planning graph as encoding a set of logical first-order interpretations. A precondition or goal formula is then regarded as reachable in a propositional layer, potentially adding new atoms to the next layer, when the set of atoms in the layer makes the formula satisfiable according to the rules of first-order logic. While this satisfiability test and the resulting heuristics turn out to be intractable, we show how a meaningful polynomial approximation can be obtained by formulating the satisfiability problem as a CSP and applying constraint propagation techniques. Experiments illustrating the computational value of planning with more expressive languages are also reported.