as far as we know, always. At least as far as human speech goes, and that's debated. If there was a time before place names, we have no record of it.

The earliest surviving texts, Sumerian cuneiform from southern Mesopotamia, includes the names of cities and rivers. Geographical names tend to be persistant, too, especially of water features. One can often track layers of language change and the arrival of newly dominant groups through changes in names of towns, while hard geography enshrines older layers and wet features older layers yet.