Abstract One drawback of Hierarchical Task Network (HTN) planning is the difficulty of providing complete domain knowledge, i.e., a complete and correct set of HTN methods for every task. To provide a principled way to overcome this difficulty, we define a simple formalism that extends classical planning to include problem decomposition using methods, and a planning algorithm based on this formalism. In our formalism, the methods specify ways to achieve goals (rather than tasks as in conventional HTN planning), and goals may be achieved even when no methods are available. Our planning algorithm, GoDeL (Goal Decomposition with Landmarks), is sound and complete irrespective of whether the domain knowledge (i.e., the set of methods given to the planner) is complete. By comparing GoDeL’s performance with varying amounts of domain knowledge across three benchmark planning domains, we show experimentally that (1) GoDeL works correctly with partial planning knowledge, (2) GoDeL’s performance improves as more planning knowledge is given, and (3) when given full domain knowledge, GoDeL matches the performance of a state-of-the-art hierarchical planner.