Many books and stories were written by Tolkien and later edited by his son Christopher, but which one was the very first of all of his Middle Earth stories?
The very very first
The first written connection to the Legendarium was a poem about Eärendel (later Eärendil), titled "The Voyage of Earendel the Evening Star", written in September 1914:
Before 1914 I wrote a 'poem' upon Earendel who launched his ship like a bright spark from the havens of the Sun.
The Letters of J.R.R. Tolkien 297: To 'Mr. Rang' (draft). August 1967
There can be little doubt that, as Humphrey Carpenter supposes (Biography p. 71), this was the first poem on the subject of Earendel that my father composed, and that it was written at Phoenix Farm, Gedling, Nottinghamshire, in September 1914.~ It was to this poem that he was referring in the letter of 1967 just cited - 'I wrote a "poem" upon Earendel who launched his ship like a bright spark
History of Middle-earth II The Book of Lost Tales Part 2 Chapter 5: "The Tale of Eärendel"
The first stanza of this poem was published in Humphrey Carpenter's J.R.R. Tolkien: A Biography in 1977, but the whole thing (an undated later version, at least) was published in The Book of Lost Tales Part Two in 1984. This poem was not, however, set in Middle-earth; the character was later incorporated into the Middle-earth mythology.
The first prose link
In 1915, Tolkien started work on The Story of Kullervo, a retelling of part of the Finnish epic poem Kalevala. While this was most assuredly not a story about Middle-earth, it's believed to have been Tolkien's first attempt at fantasy fiction, and contains the seeds of the story of Túrin Turambar. Although I don't have this book, an article in The Guardian summarizes:
The work tells the story of the son of Kalervo, “Kullervo the hapless”, as Tolkien calls him. An orphan with supernatural powers, Kullervo is brought up in the home of a dark magician, Untamo, who killed his father, kidnapped his mother and tries to kill the boy three times. When Kullervo is sold into slavery, he swears revenge, but unknowingly commits incest with his twin sister – who kills herself when she discovers what they have done.
"And before he could leap up and grasp her she sped across the glade (for they abode in a wild dwelling...) like a shivering ray in the dawn light scarce seeming to touch the green dewy grass till she came to the triple fall and cast her over it down its silver column to the ugly depths,” writes Tolkien. “And her last wail he heard and stood heavy bent on the brink as a lump of rock till the sun rose and thereat the grass grew green and the birds sang and the flowers opened and midday passed and all things seemed happy: and Kullervo cursed them, for he loved her."
"JRR Tolkien's first fantasy story to be published this month" by Alison Flood. The Guardian, August 2015
The story had previously been included in an academic paper by Dr. Verlyn Flieger, an English professor at the University of Maryland, but was first made publicly available in August 2015.
The first Middle-earth story
The first story set in Middle-earth was "The Fall of Gondolin," written in 1916 while Tolkien was on medical leave after the Battle of the Somme, though the idea had been germinating since 1912:
[T]he beginning of the legendarium, of which the [Lord of the Rings] Trilogy is part (the conclusion), was in an attempt to reorganize some of the Kalevala, especially the tale of Kullervo the hapless, into a form of my own. That began, as I say, in the Honour Mods period; nearly disastrously as I came very near having my exhibition taken off me if not being sent down. Say 1912 to 1913. As the thing went on I actually wrote in verse. Though the first real story of this imaginary world almost fully formed as it now appears was written in prose during sick-leave at the end of 1916: The Fall of Gondolin, which I had the cheek to read to the Exeter College Essay Club in 1918. I wrote a lot else in hospitals before the end of the First Great War.
The Letters of J.R.R. Tolkien 163: To W.H. Aulden. June 1955
[T]he mythology (and associated languages) first began to take shape during the 1914-18 war. The Fall of Gondolin (and the birth of Eärendil) was written in hospital and on leave after surviving the Battle of the Somme in 1916. The kernel of the mythology, the matter of Lúthien Tinúviel and Beren, arose from a small woodland glade filled with 'hemlocks' (or other white umbellifers) near Roos on the Holderness peninsula – to which I occasionally went when free from regimental duties while in the Humber Garrison in 1918.
The Letters of J.R.R. Tolkien 165: To the Houghton Mifflin Co. June 1955
The earliest drafts of what would eventually become The Silmarillion, written between 1916 and 1925/6, were published posthumously by Tolkien's son Christopher in 1983 and 1984 as The Book of Lost Tales Part One and Part Two, the first two volumes of the History Middle Earth series. The stories of Gondolin and Lúthien are both in Part Two.
The Hobbit was the first to be published.
The first-published of Tolkien's works set in Middle-Earth was The Hobbit, which was written in the early 1930s (finished by 1932) and published in September 1937.
The Silmarillion was the first to be written.
Although only published posthumously after editing by his son Christopher, Tolkien began work on The Silmarillion as early as 1914. At that point he intended it to be a collection of English legends, rather than set in an imaginary world; however, the stories he wrote then were recognisably the same ones that would become the tales of The Silmarillion.
Specifically, the first story he completed was The Fall of Gondolin, finished in late 1916.
From Wikipedia, with citations to the collection of Tolkien's Letters:
Tolkien first began working on the stories that would become The Silmarillion in 1914, intending them to become an English mythology that would explain the origins of English history and culture. Much of this early work was written while Tolkien, then a British officer returned from France during World War I, was in hospital and on sick leave. He completed the first story, "The Fall of Gondolin", in late 1916.