Bilateral single-issue negotiation is studied a lot by researchers as a fundamental research issue in agent negotiation. During a negotiation with time constraint, a negotiation decision function is usually predefined by negotiators to express their expectations on negotiation outcomes in different rounds. By combining the negotiation decision function with negotiators’ utility functions, offers can be generated accurately and efficiently to satisfy negotiators expectations in each round. However, such a negotiation procedure may not work well when negotiators’ utility functions are nonlinear. For example, if negotiators’ utility functions are non-monotonic, negotiators may find several offers that come with the same utility; and if negotiators’ utility functions are discrete, negotiators may not find an offer to satisfy their expected utility exactly. In order to solve such a problem caused by nonlinear utility functions, we propose a novel negotiation approach in this paper. Firstly, a 3D model is introduced to illustrate the relationships among utility functions, time constraints and counter-offers. Then two negotiation mechanisms are proposed to handle two types of nonlinear utility functions respectively, ie. a multiple offers mechanism is introduced to handle non-monotonic utility functions, and an approximating offer mechanism is introduced to handle discrete utility functions. Lastly, a combined negotiation mechanism is proposed to handle nonlinear utility functions in general situations. The experimental results demonstrate the success of the proposed approach. By employing the proposed approach, negotiators with nonlinear utility functions can also perform negotiations efficiently.