A detailed implementation of the Tabu search (TS) algorithm for computer-aided molecular design (CAMD) of transition metal catalysts is presented in this paper. Previous CAMD research has applied deterministic methods or genetic algorithms to the solution of the optimization problems which arise from the search for a molecule satisfying a set of property targets. In this work, proper-ties are estimated using correlations based on connectivity indices, which allows the TS algorithm to use several novel operators to generate neighbors, such as swap and move, which would have no effect with a traditional group contribution-based approach. In addition, the formulation of the neighbor generation process guarantees that molecular valency and connectivity constraints are met, resulting in a complete molecular structure. Results on two case studies using TS are compared with a deterministic approach and show that TS is able to provide a list of good candidate molecules while using a much smaller amount of computation time. (C) 2004 Elsevier Ltd. All rights reserved.