Abstract: The aim of this study is to solve the target assignment of coordinated distributed multi-agent systems. Earlier methods (e.g., neural network, genetic algorithm, ant colony algorithm, particle swarm optimization and auction algorithm) used to address this problem have proved to be either too slow or not stable as far as converging to the global optimum is concerned. To address this problem, a new algorithm is proposed which combines heuristic ant colony system and decentralized cooperative auction. Based on ant colony system, the decentralized cooperative auction is used to construct ants` original solutions which can reduce the numbers of blind search and then the original solutions are improved by heuristic approach to increase the system stability. The performance of the new algorithm is studied on air combat scenarios. Simulation experiment results show present method can converge to the global optimum more stably and faster by comparing the original methods.