Planning in the real world involves navigating vast spaces of possibilities, from finding a route through a city to searching for information online. Yet our understanding of human planning has largely come from studies involving small, simplified environments. To bridge this gap, we explored human planning in the context of the \emph{Wiki Game}, where players start on a random Wikipedia article and are tasked with clicking on hyperlinks to reach a target article with minimal steps. We hypothesized that human planners reduce the computational cost of search by employing heuristic-guided and hierarchical search strategies. Analyzing a dataset of over 75,000 games, we discovered several behavioral signatures of heuristic-guided, hierarchical search. We formalized these insights using computational models, including tree search and hierarchical tree search algorithms. We found that our hierarchical tree search model mimicked these behavioral aspects of human navigation. Moreover, the patterns in human thinking times appeared to resemble patterns in the number of search iterations in the hierarchical tree search model. Collectively, these results suggest that humans use a combination of heuristic-guided search and hierarchical decomposition to efficiently plan in large, complex conceptual spaces.