The Valaquenta ends with a description of Sauron's destruction, and so its final form cannot date from before that event. Much of the content, though, undoubtedly has earlier roots. As Christopher Tolkien notes in his foreword to The Silmarillion, '...while it contains much that must go back to the earliest days of the Eldar in Valinor, it was remodelled in later times...'
The tale's earliest origins are found in The History of Middle-earth (volume 4, The Shaping of Middle-earth). There we find an account of a 'Golden Book' held on the island of Tol Eressëa, read by a mariner named Eriol. Eriol's brief account of the first pages of the book, consisting of less than two pages of text, formed the origins of the Valaquenta.
In the earliest phases of Tolkien's work, Eriol was a pivotal character, a mortal mariner who found his way to the Lonely Isle and there learned the history of the Eldar. In later phases of the tales, though, Eriol disappears almost completely. There remains a slight possibility that his journey into the West might have inspired the last words of the Akallabêth, where we read of stories of occasional mortals sailing westward who '...had come to the lamplit quays of Avallónë'.