Dating the foundation of Edhellond is difficult, because we have two different histories that are not easily reconciled with one another. According to one account (in a note to the essay Of Dwarves and Men in volume XII of The History of Middle-earth), the haven was founded in the last years of the First Age by Sindar fleeing from the growing power of Morgoth in Beleriand. An alternative account, however, places its founding rather later, after the fall of Eregion in II 1697. This latter version of events appears in the preface to The Adventures of Tom Bombadil, but it is presented there as a tradition rather than a historical record, and so we might perhaps take the account of Edhellond's founding in the late First Age as the more reliable source.

The Old English word hæfen had various meanings, but in this context it was used specifically for a port or harbour, and it is in this older sense that Tolkien uses it with its modern spelling for the havens of the Elves. The word's original meaning as a safe harbour for ships later developed and expanded, giving rise to the more general modern English meaning of a 'haven' as any safe place or refuge.