Upon the destruction of Almaren in very ancient times, the Valar fled to Aman, and there established the realm of Valinor. Seeking to isolate themselves, they raised a great mountain fence, called the Pelóri, on the eastern coast, and set the Enchanted Isles in the ocean to prevent travelers by sea from reaching Aman.
For reasons unknown, the Valar left two lands outside the wall of the Pelóri: Araman to the northeast and Avathar to the southeast. Ungoliant, a great spider of unknown origin, had managed to escape notice in Avathar. When Melkor was released from his captivity, he fled to Avathar, scaled the mountains with Ungoliant's help, and wrought destruction of great consequence in Aman.
The first navigator to succeed in passing the Isles of Enchantment was Eärendil, who came to Valinor to seek the aid of the Valar against Melkor, now called Morgoth. His quest was successful, the Valar went to war again, and also decided to remove the Isles.
Soon after this, the great island of Númenor was raised out of Belegaer, close to the shores of Aman, and the Three Houses of the Edain were brought to live there. Henceforth, they were called the Dúnedain, or Men of the West, and were blessed with many gifts by the Valar and the Elves of Tol Eressëa. The Valar feared - rightly - that the Dúnedain would seek to enter Aman to gain immortality (even though a mortal in Aman remains mortal), so they forbade them from sailing west of the westernmost promontory of Númenor. In time, and not without some corrupting help from Sauron, the Dúnedain violated the Ban of the Valar, and sailed to Aman with a great army under the command of Ar-Pharazôn the Golden. The Valar collapsed a part of the Pelóri on this army, trapping it but not killing it. It is said that the army still lives underneath the pile of rock.
In light of this new development, the Valar decided to again isolate themselves from the other lands, but by a more decisive method than enchanted islands. The earth, at this time, was flat. They clove it in two, and made the half containing Middle-earth round, so that a mariner sailing west along Eärendil's route would simply emerge in the far east. For the Elves, however, they crafted a Straight Road that peels away from the curvature of the earth and passes to Aman. A very few non-Elves are known to have passed along this road, including Frodo Baggins, Bilbo Baggins, and possibly Samwise Gamgee and Gimli.