1590s, "act of appointing, designation," from Latin destinationem (nominative destinatio) "purpose, design," from past-participle stem of destinare "determine, appoint, choose, make firm or fast," from de- "completely, formally" (see de-) + -stinare (related to stare "to stand") from PIE *steno-, suffixed form of root *sta- "to stand, make or be firm."
From 1650s as "purpose for which anything is intended or appointed." Meaning "predetermined end of a journey, voyage, or transmission" (1813) is short for place of destination (1787) "place to which a thing is appointed or directed."