A legend is presumed to have some basis in historical fact and tends to mention real people or events. Historical fact morphs into a legend when the truth has been exaggerated to the point that real people or events have taken on a romanticized, "larger than life" quality. In contrast, a myth is a type of symbolic storytelling that was never based on fact. Throughout time, myths have sought to explain difficult concepts (e.g., the origin of the universe) with the help of common story devices, such as personification and allegories.
These words are commonly used interchangeably to refer to the fictitious nature of something. Historically and academically, however, there is a difference.
Myths are often traditional and/or religious stories that take place in a timeless past. They incorporate invented characters — usually supernatural entities, such as deities and demigods — and fantastical story elements (e.g., a flying, magic carpet), and usually take place "beyond" or "outside" of conventional timelines. Throughout history, myths have been used to explain seemingly unexplainable phenomena regarding how and why the world works the way it does or why people behave the way they do.
It is common for old myths to have once been accepted as fact, or something akin to fact, as in the case of Greek and Roman gods, the Australian Aboriginal Dreamtime, and even explanations (e.g., demonic possession) for now-curable diseases. Over time, reason and science have resulted in many mythical explanations falling out of favor until they are generally accepted to be false — mythical — stories.
Legends are also fictitious, but their origins are thought to be based on some truth. Originally, legends specifically referred to the fantastical life stories of saints (e.g., Joan of Arc), but today they refer to fantastical life stories of anyone or anything well-known. Oftentimes, the characteristics of people, particularly of heroes, in a legend are unverifiable or perhaps even false, but legends still have some basis in fact. They tend to include real people from history or take place in, say, a real war, but have obvious exaggerated or fictional elements. In legends, historical figures may have superhuman or otherwise extraordinary qualities (e.g., superhuman strength), and real events may incorporate false elements, such as a sage or fortune teller warning a hero about the events to come (foreshadowing, a story element).
Many myths and legends contain morals and supposed truths about bravery, goodness, cowardice, and evil. This is one reason why it is easy to confuse the two.
edit Examples of Myths and Legends
It is a Greek myth that Prometheus stole fire from Zeus, the chief god, and gave it to humans so that they could keep themselves warm. To punish him, Zeus chained Prometheus to a rock where his liver was eaten by an eagle every day but grew again every night. There is nothing to prove this occurred, and we do not even have a time frame to work with, so it is considered a myth.
A common contemporary myth is that a cat crossing the road in front of you brings bad luck. This is a myth, as it not based on any solid evidence.
As myths tend to include supernatural elements in a timeless past, there is no objective proof for them.
Legends are stories based on historical events or figures and hence usually exist within a certain time frame and can be placed on a real timeline. They can be verified to some degree, though it may only be to a very minor degree.
edit Fact or Fiction?
"Myth" is mostly synonymous with fiction due its lack of supporting evidence. The term "fantasy" is also synonymous in most cases.
Legends may include facts, but they are not entirely factual themselves; the truth in them has been distorted over time, usually for the sake of a good story. For example, while Pocahontas and John Smith were real people in American history, their relationship and the events that led up to their meeting have been deeply exaggerated in many stories, including in Walt Disney's 1995 animated film, Pocahontas.