In everyday language, there is no difference and they are used interchangeably. However, in a more literary or historical sense they may be used differently. I quote from the Wikipedia entry for Destiny: Fate Although often used interchangeably, the words "fate" and "destiny" have distinct connotations. Traditional usage defines fate as a power or agency that predetermines and orders the course of events. Fate defines events as ordered or "inevitable" and unavoidable. Classical and European mythology features three goddesses dispensing fate, known as Moirai in Greek mythology, as Parcae in Roman mythology, and as Norns in Norse mythology. They determine the events of the world through the mystic spinning of threads that represent individual human fates. In Islam, fate or qadar is the decree of Allah. Destiny is used with regard to the finality of events as they have worked themselves out; and to that same sense of "destination", projected into the future to become the flow of events as they will work themselves out. However as I said, I wouldn't worry about any of this for 99% of non-academic contexts, day to day they mean the same thing.

They are synonyms and can be used interchangeably. "Destiny" carries a flavor of "where you are going." "Fate" can mean that, but it also carries a flavor of "the forces that are guiding you there." "Fate" often suggests something bad, such as death, as in the word "fatal." "Destiny" can be good or bad. A fortune-teller might say to a general "Your destiny is to win a great battle," but not "Your fate is to win a great battle"--unless it was one of those ironic trick statements, in which "winning the battle" would turn out to be a bad thing. An aside: the word "destiny" isn't used so it doesn't matter, but in some branches of Protestant Christianity, "predestination" has a technical meaning in theology. The local trains make a recorded announcement that always sounds funny to me. Instead of saying "The destination of this train is Franklin," the announcement says "This train is destined for Forge Park." Technically I think this could be a correct use of the word, but it sounds comical--as if cosmic forces, and not the commuter rail company, are directing it.