This chapter charts the changing navigational landscape of the Islamic-era capitals of Egypt, from Fustat to Cairo. It recognises the navigationally strategic nature of the choice of Fustat as the first Arab-era capital of Egypt. The city’s location just above the Delta apex made it a ready control point for Nile traffic moving between Upper and Lower Egypt; the deployment of a pontoon bridge across the river enhanced that control, while the Nile-Red Sea canal also arrived at Fustat/Cairo. The chapter also examines how on-going change in the course of the Nile in the Cairo area precipitated change in the location of the main river ports serving the city.