Work to date on computational models of negotiation has focused almost exclusively on defining contracts consisting of one or a few independent issues, linear utility functions, and tractable contract spaces. Many real-world contracts, by contrast, are much more complex, consisting of multiple interdependent issues, nonlinear utility functions, and intractably large contract spaces. This paper describes a simulated annealing based approach appropriate for negotiating such complex contracts, evaluates its efficacy, and suggests some potentially promising avenues for defining more efficient algorithms for negotiating complex contracts Includes bibliographical references (leaves [14]-[15]) Work to date on computational models of negotiation has focused almost exclusively on defining contracts consisting of one or a few independent issues, linear utility functions, and tractable contract spaces. Many real-world contracts, by contrast, are much more complex, consisting of multiple interdependent issues, nonlinear utility functions, and intractably large contract spaces. This paper describes a simulated annealing based approach appropriate for negotiating such complex contracts, evaluates its efficacy, and suggests some potentially promising avenues for defining more efficient algorithms for negotiating complex contracts