The East Sea came into being after Melkor threw down the Two Lamps which destroyed Almaren and the perfect symmetry of Arda in the chaos and destruction that followed. At one point it is shown on a map of Arda after the destruction Almaren, being simply between the new Endor (Middle-earth) and the new Land of the Sun. In this very early time, the East Sea is shown as having a very simple C-shape with no connection to the also newly formed Belegaer.
By the time of the Great Journey of Elves, the maps show the East Sea as a vast curved ocean spanning thousands of miles between Middle-earth's Uttermost East and its Hither Lands to the Uttermost South, and the mysterious Dark Land, and also extending into a more narrow area between the Dark Land and the Land of the Sun. At this time, it is not known whether it had any connections to the Belegaer in the south of the world but it did share a connection with the Ekkaia in the north of the world.
After the First Age and the War of Wrath, the maps show the East Sea's part between Middle-earth and the Dark Land now known as the Inner Seas and the East Sea limited to the sea between the Dark Land's eastern coast, and the Land of the Sun's western coast. The Númenórean mariners were known to have sailed this sea coming from the darkness in the far north of the world where the Inner Seas connected with the Ekkaia. Here, they glimpsed the place of the rising Sun and sailed down to the Nether Darkness in the farthest south of the world. It probably ceased to exist after the Change of the World.