I think that anecdote is from the Anabasis by Xenophon and refers to Assyrian city of Nineveh. Babylon was still occupied during the time of Herodotus and was one of the biggest cities in the world at the time. (the book spends some time discussing Cyrus's conquest of Babylon).