Imperialist competitive algorithm is a new socio-political motivated strategy, which has better performance in continuous optimization problems. In order to apply this method to complex discrete combinatorial optimization problems appropriately, an improved imperialist competitive algorithm for solving traveling salesman problem is proposed. Based on the traditional algorithm, the proposed algorithm changes the way of forming initial empires. In the assimilation process, solutions are improved by a replacement-reconstruction policy. Then a method of adaptive adjustment of mutation probabilities is introduced in the revolution process, which enhances the search capability of the proposed algorithm. The method of colony allocation is adjusted in the imperialist competition process. An imperialist improvement mechanism is presented in order to enhance the optimization speed. The results of a set of TSP instances demonstrate the superiority of the proposed algorithm in both solution quality and convergence speed.