An immune optimization algorithm is proposed in this paper based on the immune negative selection. The algorithm NSIOA is motivatedby the negative selection mechanism in biological immune recognition. Different from the existing immune optimization methods,NSIOA constantly removes the worst solutions to get the optimal solution. Considering that removal of poor members of a populationmight lead to the loss of design information that may actually help identify better solutions in the search space, the proposed NSIOA isdesigned to keep the diversity of antibodies while removing poor members, therefore the algorithm will converge to global optimalsolution with high probability. The convergence property and the complexity of the algorithm have also been analyzed. To illustratethe efficiency of the algorithm is used in solving the travel salesman problem. The theoretical analysis and experimental results show thatthe algorithm is of a strong potential in solving practical problems.