Models of human information seeking reveal that search, in particular ad-hoc retrieval, is non-linear and iterative. Despite these findings, today’s search user interfaces do not support non-linear navigation, like for example backtracking in time. We propose QueryCrumbs, a compact and easy-to-understand visualization for navigating the search query history supporting iterative query refinement. We apply a multi-layered interface design to support novices and first-time users as well as intermediate and expert users. The visualization is evaluated with novice users in a formative user study, with experts in a think aloud test and its usage in a long-term study with software logging. The formative evaluation showed that the interactions can be easily performed, and the visual encodings were well understood without instructions. Results indicate that QueryCrumbs can support users when searching for information in an iterative manner. The evaluation with experts showed that expert users can gain valuable insights into the back-end search engine by identifying specific patterns in the visualization. In a long-term usage study, we observed an uptake of the visualization, indicating that users deem QueryCrumbs beneficial for their search interactions.