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.