"The oldest city plan discovered until now appears to be that of Çatal Höyük in Anatolia (Turkey), one of the oldest cities of the Neolithic. The map, painted onto a wall appears to represent the town itself."
Here's the map, simplified. Astonishing ... circa 6,200BC! More about early maps in general at this excellent history of information visualisation, and about this map in particular at turkeyinmaps.com.