Short version: Story means “truth” and tale means “to tell a lie”
Elaborate explanation:
The interchangeable usage of story and tale as having the same semantic connotation is relatively new and pertains solely to Present Day English. Within the English vocabulary tale has evolved and progressed natively through Germanic, West Germanic, and Anglo-Frisian which resulted in the Old English tæl. In contrast story/storie is a loanword imposed on the English language post-Norman conquest from the French estoire which developed through the Italic and Latin branch. Within the Proto-Indo-European reconstruction however, the two words came from separate roots and were not used interchangeably (nor should they be now). What becomes apparent in the history of the two words is the ‘truth’ aspect present in a story and that a tale brings forth a lie. For the purpose of understanding how each word was being defined by lexicographers I have examined dictionaries as far back as 1678 and have found that tale has been used to define story and vice versa. At times both were being used in defining history. The concept “narrative” is however at the base of all three within all dictionaries at all historical points thus being the cohesive agent of all three.
Tale evolved naturally into the English language. The Proto-Indo-European *del meaning “to recount/count” developed into the Germanic Talō which then separated into North Germanic and West Germanic talu (“*del”). North Germanic later divided into Old Norse/Old Icelandic which contains in its dictionary Tal as noun meaning “Talk, parley, conversation. 2. Speech, language. Tala 1. Discourse, speech 2. Tale, number and Tala as verb meaning to talk or speak. To record and to tell.” This shows the word had maintained its semantic value throughout this division. Anglo-Frisian tælu developed into the Old English tæl. In Joseph Bosworth’s Anglo-Saxon Dictionary tæl appears as noun to be “a tale, number, series” but also “evil speaking, calumny, detraction…attack with blasphemy.” Interestingly enough “tale” as a number system finds its way into Portuguese as tæl coming from the Malay tahil meaning “any of several monetary units equal to the equivalent weight in silver.” This is quite amusing as it develops through a different branch and comes to a semantically-relevant homophonic word which in Old English is tæl. Another homophone of “tale” being “tail” maintains the same semantic value in Old Norse as it is tagl meaning the tail of an animal which at the same time in Old English was taegel also meaning tail. Tælan as a verb meant “to blame, rebuke, reprove, reproach, censure, accuse. To speak evil. To slander, to treat with contempt, scorn, insult, mock.” Throughout this division of language, the word brought along with it the implication that one would “recount” or “speak.” There is however a difference between speaking and telling. Elizabeth Closs Traugott writes in her work Regularity in Semantic Change that “tell primarily introduces a narrative…[and that] the reorganization of the lexicon occurred in Middle English with the introduction of talk (an early Frisian term) and the focusing of tell on verbal action (in OE tellan meant primarily ‘count’ or ‘recount; in sequence, i.e. ‘narrate’). Talk is the only word in English borrowed from Lithuanian, which has talkas for ‘talk’ and tulkot for ‘interpreter.’ Russian tolk meaning ‘sense’ and the verb tolkovant-‘to interpret.’ Thus tale as it became in Middle English, though it remained ‘an account’ it also brought along with it a trace of deceit and evil-speaking.
Story on the other hand, originated from the PIE root *wid-tor meaning “to know” or literally translated “to see.” This became in Latin historia which was a “narrative of past events, an account.” Istō/Istoc (root of historia) meant “to the place where you are, to the point you have reached, to this place.” The Latin equivalent for what we now use the word “story/tale” was narratio or fabulo, which we know to be ‘narrative’ or ‘fable’ (quite a different topic altogether). Historia divided into the Romance languages and in French became estoire which literally meant “a chronicle, a history.” The introduction of stoire/story into the English language occurred post-Norman Conquest in Middle English.
Looking at past lexicographers and how they defined story, tale or even history, it becomes apparent that all definitions contain “narrative” as a key concept of each word’s semantic connotation. Samuel Johnson in 1806, E. Cobham Brewer in 1882, and Rev. Walter W. Skeat in 1910 all use tale when defining story and vice versa. This brings to question why the merging of the two separate words occurred, and why the ‘deceit’ in what was previously known in OE tæl was no longer part of the definition of tale. Though the two separate are being used interchangeable tale did maintain the lie in other tangential words sprung from it up to Present Day English. Looking for instance at Johnson’s definition of storyteller and talebearer the distinction becomes much clearer. Johnson defines storyteller as “[story and tell] One who relates tales in conversation, a historian, in contempt” and yet he defines talebearing as “[tale and bear] The act of informing; officious or malignant intelligence.” Talebearing thus implies a gossip-like nature versus one delivering an informative speech.
The most interesting form in which the two words have appeared within a text together as “tale-story” was within Thomas Fuller’s The History of the Worthies of England. It is the only text identified by the OED to have used the words together (hyphened). It is worth glancing at how Fuller used this hyphenated word and within what context (Fuller is speaking about Sutton of Salsbury and how he became wealthy based on an old pamphlet –advertising):
“Thus these mongrel pamphlets (part true, part false) do most mischief. Snakes are less dangerous than lampreys, seeing none will feed on what is known to be poison. But these books are most pernicious, where truth and falsehoods are blended tougher, and such a medley-cloth is the tale-story of this clothier.”
Mongrel, medley-cloth, and tale-story are used interchangeably by Fuller containing the same semantic implication. Mongrel he himself emphasizes to be “part true, part false” and medley-cloth was “a type of cloth woven with wool of different colours or shades mixed in the thread.” Thus, tale-story within this context is the mixture of a truth and a falsehood which means story remained a more reliable account and tale still brought along with it the ‘calumny’ and deceit encountered in the Old English even mid-17th century. Thomas Fuller wrote the book in the late 1650s and passed away in 1661. The book was published posthumously in 1662.
Joint words like tall-tale and fairy-tale emphasize the different aspects of a lie a tale contains. For instance the word tall is a figurative word within the English language which stands for something being exaggerated and has been widely used. Yet one rarely encounters “tall-stories” or “fairy-stories” because the implication would be that one had been there and the content of the account is based in a truth or a biographical occurrence that had once happened and simply been retold. Should one recount a truth with exaggeration it would no longer be a story, rather it would become a “tall-tale” and he/she would be Johnson’s talebearer rather than his storyteller.
This semantic property of ‘truth’ to story remains in Present Day English yet within narrower contexts. Authors like Alice Munro who publish a collection of short narrative accounts are not summed up by publishers as ‘short tales’ nor do they write that on the cover or on the title page. Rather, due to the mature content and the respect attributed to the content, the collected works would be referred to as Short Stories thus implying that parts of these narratives are true and have been appropriated for publication. Tales on the other hand are encountered within texts intended for children (beyond fairy tales) or within contexts where the lie is known to be there. For instance, Gabriel Garcia Marquez wrote his autobiography Living To Tell the Tale, with clear hindsight of what has been professed about his art. Magical Realism has been treated as “the truth of a five-year-old” or “telling a lie with a brick face” (as my English professor, Nick Mount, used to say). Evidently, even in present day narrative content with a more deceitful tone or intended for children is more likely to be labelled as a tale rather than a story.
Thus, by looking at the two words individually and tracing them to their reconstructed Indo-European root in addition to examining how they have been defined by lexicographers at various historical points it becomes evident that story and tale cannot always be used interchangeably (or at least they shouldn’t). The two are not only different but they are contradictory in meaning for one means “truth/to know” while the other means “a lie/to deceive.” The credibility attached to stories has remained through to Present Day English and the exaggerated (somewhat derogatory) connotation remains attached to tales. The possibility that idioms within the English language have contributed to the semantic property of a tale leaves much room for exploration on this topic.
Works Cited: Fuller, Thomas D.D. The History of the Worthies of England (1840), “*del” The American Heritage Dictionary of the English Language, Derocquigny, Jules. A Contribution to the Study of the French Element in English (1904),“Isto/Istoc” Oxford Latin Desk Dictionary (2005), “Medley-cloth” The OED Online, Nick, Mount “Gabriel Garcia Marquez and Magical Realism” (Lecture, 2011), Lemon, Rev. George William. English Etymology or A derivative dictionary of the English language: in two alphabets (1783), Murray, James A.H. “Oxford English Dictionary.” X, XI. (1969-70), Philips, Edward. The New World of Words (1684), Skeat, Rev. Walter W. An Etymological Dictionary of the English Language (1910), “storyteller” n.f. Def 1. Johnson’s Dictionary of the English Language (1806), “tael” Def.1. Joseph Bosworth’s An Anglo-Saxon Dictionary (1954), “taelan” Def.1. Joseph Bosworth’s An Anglo-Saxon Dictionary (1954), “talebearing”n.f. Def.1. Johnson’s Dictionary of the English Language (1806), Traugott, Elizabeth Closs. Regularity in Semantic Change (2005), Tulloch, Alexander R. Word Routes: Journeys Through Etymology (2005), “*wid-tor” The American Heritage Dictionary of the English Language (2013), Zoega, Geir T. A Concise Dictionary of Old Icelandic (1926)
For the month of October I binge-listened to the entire 
The podcast won best history podcast last year. The podcast is accompanied by music throughout and occasional commercials. New episodes are released every two weeks on Mondays. If you’re like me and late to the party just be happy. It’s a GOOD party, and you get to binge, which is awesome! The musical accompaniment is by Chad Lawson, who will soon release an album featuring the songs from LORE called 
Just as I was deep mid-podcast, on October 15, Amazon Prime Video released 
This was actually my favourite format of the four, which I’ll explain at length below. It maintains the ‘cleanliness’ of the book, but it also has Mahnke’s voice and some musical effects which I loved from the Podcast. I got this from 
This book is made of the transcripts from the LORE Podcast mentioned above and edited in such a way that results in a very smooth transition from one tale to the next. The book itself is a mere fraction of what is to be a longer series, published by 
Infinite Text 