The Madaba Map, dated to between 542 and 570 CE, has been preserved in the apse of the Church of St. George in Madaba, Jordan. To quote the Wikipedia article on the map:
The mosaic map depicts an area from Lebanon in the north to the Nile Delta in the south, and from the Mediterranean Sea in the west to the Eastern Desert. Among other features, it depicts the Dead Sea with two fishing boats, a variety of bridges linking the banks of the Jordan, fish swimming in the river and receding from the Dead Sea; a lion (rendered nearly unrecognisable by the insertion of random tesserae during a period of iconoclasm) hunting a gazelle in the Moab desert, palm-ringed Jericho, Bethlehem and other biblical-Christian sites. The map may partially have served to facilitate pilgrims' orientation in the Holy Land. All landscape units are labelled with explanations in Greek.
A combination of folding perspective and aerial view depicts about 150 towns and villages, all of them labelled. The largest and most detailed element of the topographic depiction is Jerusalem, at the centre of the map. The mosaic clearly shows a number of significant structures in the Old City of Jerusalem: the Damascus Gate, the Lions' Gate, the Golden Gate, the Zion Gate, the Church of the Holy Sepulchre, the Tower of David and the Cardo Maximus. The recognisable depiction of the urban topography makes the mosaic a key source on Byzantine Jerusalem. Also unique are the detailed depictions of cities such as Neapolis, Askalon, Gaza, Pelusium and Charachmoba, all of them nearly detailed enough to be described as street maps.
For more on the map, see the article by Aharon Jaffe on the Israeli Ministry of Foreign Affairs website. He writes:
During the Byzantine period (324 until the Persian conquest of 614 ce), Madaba was on the eastern border of the province of Palaestina, the smallest of the provinces of the Byzantine Empire. It was one of four cities (together with Heshbon, Philadelphia modern Amman and Jerash) on the western border of the Byzantine province of Arabia, which shared a northern border with Palaestina Secunda, in the centre with Palaestina Prima, and in the south, with Palaestina Tertia. These were the main districts of the province, which were later divided into sub-districts.
There are a number of very good websites on the Madaba Map, especially one produced by the Franciscan Order, the Custodia Terrae Sanctae - http://www.christusrex.org/www1/ofm/mad/index.html. Quoting from this web site:
It is the commonly accepted view among scholars that the Madaba map depends heavily on Eusebius' gazetteer of biblical places, the Onomastikon. One might even take the view that the Madaba map is but a 'revised edition' of the Onomastikon, illustrated and brought up to date by the addition of churches and pilgrim places that in Eusebius' time did not exist, and by the juxtaposition of additional sources for areas not covered by Eusebius, e.g. a map of the Egyptian Delta or a road map.