After Númenor was destroyed by Eru Ilúvatar because of the deeds of their King, the world was changed and made into a round sphere. Aman was removed from the circles of the world and the seas bent so that no man could ever find the Undying Lands ever again. In place of Aman these New Lands were created in the west.
Sometime at the end of the Second Age (between the Akallabêth and the War of the Last Alliance), they were discovered by the great mariners of the Dúnedain living in Middle-earth yearning for the west or searching for the Isle of Meneltarma. Coming upon them, they found these New Lands to be much like the old ones where things were mortal and not forever. It is not known whether men ever returned to these lands afterwards but in the finding of these lands, men did discover that the world was now round.
The shape and size of these lands has not really been made clear by the Akallabêth but since mariners were able to sail further west returning to their beginning, it is possible that these lands may be very large islands of a sort. They seem to correspond with the Americas, although whether they were indeed two continents (as speculated in the image above) or a single landmass has never been made clear.
Some fans have speculated that these "New Lands" were a remade version of the Land of the Sun to the east of Middle-earth, and that this particular landmass no longer existed by the Third Age. Certainly no maps of the Third Age extend that far eastward or westward, so we do not know.