"Destiny" vs. "Fate"

Fate is from the Latin fatum, which means "that which has been spoken."
Destiny is from the Latin destinare, which means "to make firm" or "to establish."

I agree with Billare that fate has a more fatalistic feel (fatalistic also comes from fatum), as it has a deeper implication of one's end being decided by a separate entity.

_{Reference: the NOAD.}

From Wikipedia:

...fate relates to events of the past and is proven to be true and unalterable, whereas destiny relates to the probable to almost certain future. Note that it is only almost certain and not absolutely certain, allowing for change to occur. This can be seen in our common language usage, e.g. "His calling, his destiny is to be a doctor." Will he definitely be a doctor? Well, it remains to be seen.

I apologise in advance for the lack of original examples and more authoritative sources, but perhaps further research into the use of 'fate' and 'destiny' in both classic and modern literary texts will help.

To me, "fate" sounds more likely to be used in a negative context, while "destiny" is (generally) more positive. Headline examples:

Waiting for word on fate of kidnapped American

Super Bowl win was destiny for Saints

As reported by the Online Etymology Dictionary, the etymology of the words is the following:

• fate
  Late 14th century, from Latin fata, neuter plural of fatum ("prophetic declaration, oracle, prediction," thus "that which is ordained, destiny, fate"), literary "thing spoken (by the gods)," from neuter past participle of fari ("to speak"), from PIE *bha- ("speak"). The Latin sense evolution is from "sentence of the Gods" (Greek theosphaton) to "lot, portion" (Greek moira, personified as a goddess in Homer), also "one of the three goddesses (Clotho, Lachesis, and Atropos) who determined the course of a human life." Related: Fated; fating. The native word was wyrd.

• destiny
  middle 14th century, from Old French destinée ("purpose, intent, fate, destiny; that which is destined,") feminine past participle of destiner, from Latin destinare ("make firm, establish"). The sense is of "that which has been firmly established," as by fate.

To supplement the etymology-centered answers that snumpy and kiamlaluno provide, I offer these discussions from three synonym dictionaries of quite different ages. First, from James Fernald, English Synonyms, Antonyms and Prepositions (1896):

Fate is heathen, an irresistible, irrational power determining all events with no manifest connection with reason or righteousness; ...

This characterization is in contrast with the book's description of the words foreordination and predestination, which Fernald asserts "are Christian, denoting the rational and righteous order or decree of the supreme and all-wise God." Destiny, we may suppose, is intimately connected with predestination in this second category of words, although Fernald does not devote any space to it. Certainly there was a strong religious strain in the term manifest destiny, popularized in the 1840s in expansionist political discourse in the United States. For example, in "Speech of Hon. C. W. Cathcart, of Indiana, on the Oregon Question" (February 6, 1846):

We are asked how we expect to dispossess the Hudson Bay Company of her pallisade forts in Oregon? Is it possible that an American can doubt upon this point? Prepare yourself and demand their surrender, as Ethan Allen did the surrender of Ticonderoga, "in the name of the Great Jehova and the Continental Congress." And this reminds me of the sneers of some gentlemen in relation to what they call our "western doctrine of manifest destiny." Do gentlemen reflect where they place themselves by these sneers? Do they forget that the Savior of mankind has said that a "sparrow shall not fall to the ground without your Father?" And yet we are asked, where is the clause in Adam's will which gives us this territory? Apart from the "book title," which is "clear and unquestionable," we see it written in letters of living light in everything which surrounds us—in that merciful dispensation, full of charity and love, towards the fallen children of Adam—of a just and omniscient God, who has given to man that control of the elements, the effect of which is to bring the remotest parts of our vast country into practical propinquity. The iron horse, (the steam car,) with the wings of the wind, his nostrils distended with flame, salamander-like vomiting fire and smoke, trembling with power, but submissive to the steel curb imposed upon him by the hand of man, flies from one end of the continent to the other in less time than our ancestry required to visit a neighboring city; while by the magnetic telegraph the lightning of heaven is made subservient to the will of man in annihilating space.

Thus, the destiny of the United States to rule North America from ocean to ocean, by Providential decree, is manifested in part by God's granting mankind the railroad train and the telegraph.

A much later discussion of fate and destiny appears in S.I. Hayakawa, Choose the Right Word: A Modern Guide to Synonyms (1968):

destiny, fate, fortune, lot These words refer to a situation or outcome as though it were fixed or predetermined. Destiny is the most general and least specific of the these. It can suggest an occult prearrangement of the future: No man can escape his destiny. At the other extreme, it can refer simply to a result, without suggesting any forces at work beyond cause and effect: Congressmen meeting to decide the destiny of the abortion reform law. Fate, by contrast, is much stronger in implications of a deterministic pattern. Where destiny might point to a desired goal without rejecting the notion of free will, fate points to an outcome, good or bad, as though choice, chance, or cause and effect played no part in its working out: Oriental religions that advise man to accept his fate without bitterness. Even when weakened by use to refer merely to result, the word often suggests an unpleasant outcome: mountain-climbers who met a disastrous fate.

In Hayakawa's view, destiny can work hand-in-hand with effort and intentionality, but fate is a done deal: Oedipus (unwittingly) works toward his destiny, because he can't escape his fate.

A third treatment appears in Merriam-Webster's Dictionary of Synonyms (1984):

fate, destiny, lot, portion, doom are comparable words when they denote the state, condition, or end which is decreed for one by a higher power. Fate presupposes such a determining agent or agency as one of the ancient goddesses called Fates, the Supreme Being, or the law of necessity; the term usually suggests inevitability and, sometimes, immutability {he either fears his fate too much, or his deserts are small, that dares not put it to the touch to gain or lose it all—Montrose} {let us, then, be up and doing, with a heart for any fate—Longfellow} {he maintained that the fate of the Southern Negro depended on his right to protect himself by voting—C.L. Thompson} Destiny may imply an irrevocable determination or appointment (as by the the will of the gods or of God); even in this sense, however, it carries little or no suggestion of something to be feared; on the contrary, it may even imply a great or noble state or end {the conception of a lordly splendid destiny for the human race—Russell} {Lawrence was ... unescapably an artist .... There were moments when he wanted to escape from his destiny—Huxley} Destiny may also apply be applied to whatever one envisions as his end or goal, sometimes retaining a slight implication that it is, or has the inevitability of, the will of God. {the intoxication of victory swept Hitler's fears away; they were never voiced again, drowned with cries of defiant belief in his destiny—Times Lit. Sup.}

It appears that the distinction (proposed by Fernald) between heathen inevitability (fate) and Christian foreordination (destiny) is long gone, if it ever existed in popular usage. In my experience, an expression like "You can't change destiny" means essentially the same thing as the expression "You can't change fate." But as Merriam-Webster's commentary suggests, there is sometimes a kind of grandeur in destiny that seems more often lacking in fate, and this may reflect an older distinction along Fernald's lines.