What is the first use of the term "Middle-earth" in Tolkien's works?

Question

Tolkien was writing stories set in his legendarium before a lot of his concepts and nomenclature was finalized.

What was the first of Tolkien's writings to use the term "Middle-earth"?

Answer 1

First usage.

Tolkien began to use the term "Middle-earth" in the early 1930s in place of the earlier terms "Great Lands", "Outer Lands", and "Hither Lands" to describe the same region in his stories. "Middle-earth" is specifically intended to describe the lands east of the Great Sea (Belegaer), thus excluding Aman, but including Harad and other mortal lands not visited in Tolkien's stories. Many people apply the name to the entirety of Tolkien's world or exclusively to the lands described in The Hobbit, The Lord of the Rings, and The Silmarillion. - Source

Tolkien revised his chronology numerous times. The Annals of Valinor were written in the early 1930s. - Source_1 & Source_2

The History of Middle-Earth is a 12 volumed series and in the 4th one (The Shaping of Middle-Earth) section 6 explains the earliest Annals of Valinor which was written in early 30s but published in the late 80s.

Following part is from The Annals of Valinor. You can find the entire text in the source.

In the Valian Year 1000, after the building of Valinor, and Valmar the city of the Gods, the Valar brought into being the Two Trees of Silver and of Gold, whose bloom gave light unto Valinor. But all this while Morgoth had dwelt in the Middle-earth and made him a great fortress in the North of the World; and he broke and twisted the Earth much in that time. Source

The answer is entirely based on the power of deduction.

Answer 2

Both "Ambarkanta" & "Annals of Valinor", but it's unknown which one came first.

As per Christopher Tolkien (Tolkien's son and literary executor), the first works of Tolkien's to include the term Middle-earth were the Ambarkanta and the Annals of Valinor.

"Middle-earth" is first found in the Ambarkanta and in the Annals of Valinor, which belong to the same period but cannot be dated relative to one another.
_{(Christopher Tolkien - The Shaping of Middle-earth (HoME4) - Commentary on the Ambarkanta)}

Both of these writings can be found in volume 4 of The History of Middle-earth.

Above the Earth lies the Air, which is called Vista, and sustains birds and clouds. Therefore it is called above Fanyamar, or Cloudhome; and below Aiwenore or Bird-land. But this air lies only upon Middle-earth and the Inner Seas, and its proper bounds are the Mountains of Valinor in the West and the Walls of the Sun in the East.
_{(The Ambarkanta - The Shape of the World)}

In the Valian Year 1000, after the building of Valinor, and Valmar the city of the Gods, the Valar brought into being the Two Trees of Silver and of Gold, whose loom gave light unto Valinor.
But all this while Morgoth had dwelt in the Middle-earth and made him a great fortress in the North of the World; and he broke and twisted the Earth much in that time.
_{(The Annals of Valinor (earliest version))}

Bonus: First published usage

The first published work of Tolkien's to include the term Middle-earth was The Lord of the Rings.

Yet it is clear that Hobbits had, in fact, lived quietly in Middle-earth for many long years before other folk became even aware of them.
_{(The Lord of the Rings - Prologue)}

Answer 3

By an extention, Tolkien first referred to "middle-earth" in his 1914 poem entitled "The Voyage of Eärendel the Evening Star".

Éarendel sprang up from the Ocean’s cup

In the gloom of the mid-world’s rim;

From the door of Night as a ray of light

Leapt over the twilight brim,

And launching his bark like a silver spark

From the golden-fading sand;

Down the sunlit breath of Day’s fiery Death

He sped from Westerland.

This poem (which could be considered the first of Tolkien's legendarium writings) was inspired by an Anglo-Saxon poem Crist which actually used the term middangeard (middle-earth).

http://en.wikipedia.org/wiki/Middle-earth

http://www.tolkiensociety.org/2014/09/100-years-of-middle-earth