Rewriting software using Agile methodologies

Question

Suppose you have to rewrite an entire application using Agile methodologies, how would you do it?

I guess you could write a big bunch of user stories based in the behavior of your current system. And then implement them in small iterations. But this wouldn't mean that we have the requirements UP FRONT??

Also, when would you start releasing? Agile says we should release early and often, but it doesn't make much sense to release before the complete rewrite has been completed.