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.