Valinor was also known as the Undying Lands as only immortal souls were allowed to reside there, with some exceptions when it came to the bearers of the One Ring, and it is said, Gimli also accompanied his friend Legolas to these lands.
Each of the Valar had their own region of the land where they resided and altered things to their desire. Yavanna, the Vala of nature, growth, and harvest, resided in the Pastures of Yavanna in the south of the island. Oromë, the Vala of the hunt, lived in the Woods of Oromë to the north-east of the pastures. The forest was home to many creatures which Oromë could track and hunt. Nienna, the lonely Vala of sorrow and endurance, lived cut off in the far west of the island in the Halls of Nienna where she spent her days crying, looking out to sea. Just south of the Halls of Nienna and to the north of the pastures there were the Halls of Mandos. Mandos, the brother of Nienna, was the Vala of the afterlife. All inhabitants of Middle-earth went to the Halls of Mandos should they happen to die, mortals and immortals alike (Tolkien's immortals could be killed although they did not die of old age) although it was said that in death as in life, they were separated. Also living in the Halls of Mandos was his spouse Vaire the weaver, who wove the threads of time.
To the east of the Halls of Mandos was the Isle of Estë, which was situated in the middle of the lake of Lórellin which in turn was situated to the north of the Gardens of Lórien (not to be confused with Lothlórien in Middle-earth which was created by the same Valar, Lórien also known as Irmo, the Vala of dreams). Estë and Lórien being husband and wife lived close together. To the north of this were the Mansions of Aulë the smith Vala who was spouse to Yavanna. In the north-east lay the Mansions of Manwë and Varda, the two most powerful Valar, also married. To the west of them stood the Two Trees of Valinor, Telperion and Laurelin. The entire great continent of Valinor was surrounded on three sides (excluding the north which was instead protected by ices flows) by a huge mountain range called the Pelóri mountains. In the extreme north-east, past the mountain range was the pass of Helcaraxë, a vast ice sheet which in the beginning, before Valinor was risen after the fall of Númenor in to the sky to prevent people from travelling there, joined the two continents of Valinor and Middle-earth. In the beginning, some Elves, tricked by the evil god Melkor passed along this pass to go back to Middle-Earth, among those was Galadriel who featured in the War of the Ring. Those who took this pass were not allowed back to Valinor for many years, but in the end pity was taken on them when Middle-earth began to fade and pass into the age of men and they were allowed to pass back to the Undying Lands of their own accord when they felt ready to do so.
Also, for a time before the ruin of Númenor, a long chain of small islands called the Enchanted Isles ran the full length of the east coast of the continent. These were created to prevent anyone, mortal or immortal, from reaching the land by sea.
After the destruction of Númenor, the Undying Lands were removed from Arda so that Men could not reach them and only the Elves could go there by the Straight Road and in ships capable of passing out of the Spheres of the earth. By special permission of the Valar, the Hobbits Frodo Baggins, Bilbo Baggins, and Samwise Gamgee were also permitted to go to Valinor, as well as Gimli the Dwarf.
It has been suggested that the concept was based off Hy Brasil, a mythical land that can reputedly be seen off the coast of Ireland for one day in every seven years.