1510s, "to send off, send to a destination," usually implying urgent importance or haste, from Spanish despachar "expedite, hasten" or cognate Italian dispacciare "to dispatch." For first element, see dis-.
The second element apparently has been confused or corrupted, and its exact source and meaning is uncertain. One proposal is that it is Vulgar Latin *pactare "to fasten, fix" or *pactiare. Another says it is Latin -pedicare "to entrap" (from Latin pedica "shackle;" see impeach), and the Spanish and Italian words seem to be related to (perhaps opposites of) Old Provençal empachar "impede." See OED for full discussion.
Meaning "get rid of promptly by killing" is attested from 1520s; that of "attend to, finish, bring to an end, accomplish" is from 1530s. Related: Dispatched; dispatching.
1540s, "dismissal after settlement of business," from dispatch (v.). Meaning "speed, haste" is from 1570s. Sense of "a written message sent speedily" is first attested 1580s; that of "a sending off or away" is from c. 1600.