Tabu search is one of the most ee tive heuristi s for lo ating high-quality solutions to a diverse array of NP-hard ombinatorial optimization problems. Despite the widespread su ess of tabu searh, resear hers have a poor understanding of many key theoreti al aspe ts of this algorithm, in luding models of the high-level run-time dynami s and identi-  ation of those sear h spa e features that in uen e problem diÆ ulty. We onsider these questions in the ontext of the job-shop s heduling problem (JSP), a domain where tabu sear h algorithms have been shown to be remarkably ee tive. Previously, we demonstrated that the mean distan e between random lo al optima and the nearest optimal solution is highly orrelated with problem diÆ ulty for a well-known tabu sear h algorithm for the JSP introdu ed by Taillard. In this paper, we dis uss various short omings of this measure and develop a new model of problem diÆ ulty that orre ts these de ien ies. We show that Taillard's algorithm an be modeled with high delity as a simple variant of a straight- forward random walk. The random walk model a ounts for nearly all of the variability in the ost required to lo ate both optimal and sub-optimal solutions to random JSPs, and provides an explanation for dieren es in the diÆ ulty of random versus stru tured JSPs. Finally, we dis uss and empiri ally substantiate two novel predi tions regarding tabu sear h algorithm behavior. First, the method for onstru ting the initial solution is highly unlikely to impa t the performan e of tabu sear h. Se ond, tabu tenure should be sele ted to be as small as possible while simultaneously avoiding sear h stagnation; values larger than ne essary lead to signi ant degradations in performance.