Abstract: Automated negotiation is a key problem in multi-agent systems (MAS). It means establishing contracts for working together between agents. Now, in many cases these contracts consist of multi-issue, which makes the negotiation more complex than dealing with just one-issue. In multi-issue negotiation, how to conduct automated negotiation quickly and high-efficiently has become an important problem that we must deal with in MAS. A bilateral multi-issue automated negotiation model (MN) is proposed, and then an accelerating chaos evolution algorithm for the bilateral multi-issue automated negotiation is given. In this method the chaos mechanism is introduced into evolution and then algorithm constantly shrinks the searching area to accelerate method. By this way, the algorithm avoids premature converging to local Nash point, and solves slow convergence of multi-issue negotiation and chaos evolution algorithm. Theory analysis and experiments indicate that this method can fast and more efficiently converge to the global optimal numerical value in the field at probability of 1.