We describe HDL, an algorithm that learns HTN domain descriptions by examining plan traces produced by an expert problem-solver. Prior work on learning HTN methods requires that all the methods' information except for their preconditions be given in advance so that the learner can learn the preconditions. In contrast, HDL has no prior information about the methods. In our experiments, in most cases HDL converged fully with no more than about 200 plan traces. Furthermore, even when HDL was given only half the plan traces it required to fully converge, it usually was able to produce HTN methods that were sufficient to solve more than 3/4 of the planning problems in the test set.