CNC machining centers store multiple tools required for completing operations on jobs in a tool changer. The tool indexing problem is one of assigning tools to slots in the tool changer so that tool changeover time is minimised, thus making the overall processing of jobs efficient. We present a characterisation of optimal tool assignments to slots in practical situations when the number of tools to be assigned is smaller than the number of available slots. We use this characterisation to prove that the tool indexing problem is 𝒩𝒫-complete. We then present a tabu search algorithm called SITS to solve the tool indexing problem. This algorithm is efficient, as it uses a larger neighbourhood than common tabu search algorithms and makes use of techniques that significantly speed up neighbourhood search for this problem. Statistical analysis of results from our computational experiments show that SITS is better than the present state of the art in terms of solution costs, especially for large instances. It is thus a serious contender for solving practical tool indexing problems.