The curious origin of Tolkien's story Smith of Wootton Major (the best of his short fiction, in my humble opinion), should probably be mentioned in this thread, since it is a good example of the serendipitous ways in which his worlds expanded (even though Smith is not part of the legendarium, per se).
In around 1964, Tolkien contracted to write an Introduction to George MacDonald's Golden Key (probably because he had previously praised MacDonald, and that book in particular). The problem was, when Tolkien went to take another look at the book, he found that he disliked it intensely. Fortunately, the project ended up being abandoned, which saved him from either having to back out, or write a critical essay (in the sense of expressing a negative opinion), which would not have exactly served to help sell the book.
In the course of trying to draft this Introduction, Tolkien attempted to describe what Faery was by giving an Illustration. He started to outline a story that Faery could be put into. However, the story quickly took on a life of its own, and the next thing he knew, he had abandoned the Introduction to focus on the story. And that is how Smith of Wootton Major came into being.
For any interested in learning more about this, and tracing the creation of this excellent little fable, I strongly recommend the extended edition book of Smith of Wootton Major, edited by none other than Verlyn Flieger. It is, in its way, as interesting a study as Rateliff's History of the Hobbit. It was only released by Harper Collins; there is no Houghton Mifflin American edition, but it is still easily obtainable through Amazon.
"Among the tales of sorrow there are yet some in which amid weeping there is joy and under the shadow of death light that endures."