1590s, "to communicate with another or others in search of mutual agreement," a back-formation from negotiation, or else from Latin negotiatus, past participle of negotiari "carry on business, do business," from negotium "a business, employment, occupation, affair (public or private)," literally "lack of leisure," from neg- "not" (from PIE root *ne- "not") + otium "ease, leisure," a word of unknown etymology.
Transitive sense of "arrange for or procure by negotiation" is from 1610s. In the sense of "handle, manage, tackle successfully" (1862), it at first meant "to clear on horseback a hedge, fence, or other obstacle" and "originated in the hunting-field; those who hunt the fox like also to hunt jocular verbal novelties" [Gowers, 1965]. Related: Negotiated; negotiating.