Before the time of the Two Trees of Valinor, and even before the Valar came to Valinor, they dwelt on the green island of Almaren in the Great Lake. In the mists of time, long before the awakening of Elves or Men, the Valar dwelt east of the Sea in Middle-earth. This was a time called the Spring of Arda, when Arda was lit by the two Lamps of the Valar, and Almaren lay in the central regions of the World, where the light of the two Lamps mingled.
Of the details of Almaren we know little - there was green grass on the island, and the Valar had a 'dwelling' there, which presumably constituted a city, or at least a town. In the history of the Valar, Almaren was known as the place where Tulkas wed Nessa.
Of much greater importance, though, is the fact that Almaren was the site of the Valar's first major defeat at the hands of Melkor: he loosed his forces secretly from his northern fortress of Utumno (then newly delved). Both the Lamps of the Valar were thrown down and destroyed, and Almaren lay in ruins. Tulkas gave chase, but Melkor escaped into the dungeons of Utumno.