We describe the design and implementation of online bi-lateral negotiations. The negotiation middleware can be used in a stand-alone mode for electronic commerce and to provide support for other multilateral trading systems such as auctions and RFQ?s, where it is integrated with bidding and bargaining processes. The negotiation engine design uses the state-machine formalism. It supports multi-attributed bids and offers and a wide variety of evaluation schemes. Since various users of the system may need different negotiation protocols to achieve their differing objectives such as rapidly concluding the deal or finding the mutually optimal solution, the design of the negotiation engine supports the choice of a negotiation protocol best suited for the objective. The negotiation engine has been prototyped on WebSphere Commerce Suite, IBM?s ecommerce middleware.